#include <bits/stdc++.h>
#include <iostream>
#include<string.h>
#include<string>
#include <sys/time.h>
// MEHMET ERIM KMP
using namespace std;
void computeLPS(string pattern,int lps[])
{
int len = pattern.size();
lps[0] = 0;
int i = 0, j = 1;
while (j < len) {
if (pattern[i] == pattern[j]) { // if i and j is match value of i+1 and lps(j) write
i++;
lps[j] = i;
j++;
}
else
{
if (i != 0) { // if i is not at index of 0 go back
i--;
}
else // if i is beginning, put 0 to LPS
{
lps[j] = 0;
j++;
}
}
}
}
void KMPSearch(string text, string pattern)
{
int m = pattern.size();
int n = text.size();
int lps[m];
computeLPS(pattern, lps);
int i = 0;
int j = 0;
while (i <= n) {
if(j==m){
printf("Pattern found at index %d \n", i-j);
}
if (pattern[j] == text[i]) {
j++;
i++;
}else{
if(j == 0){ // if i at first characters in the pattern, shift 1 steps
i++;
}else{ // if i not at first character in the pattern, shift until lps values
i+= (j)-lps[j-1];
}
j = 0; // if any missmatch j set default value of 0
}
}
}
int main()
{
string pattern = "AAA";
string text = "AAAA";
KMPSearch(text,pattern);
return 0;
}