#include<stdio.h>
#include<string.h>
#include<string>
#include <sys/time.h>
#include <iostream>
#define NO_OF_CHARS 256
// MEHMET ERIM FSM
using namespace std;
void createTable(string pattern,string patternCharacter,int TF[][NO_OF_CHARS]){
// string pattern = "abcabd";
// string patternCharacter = "abcd";
int size =pattern.size();
// int TF[size+1][NO_OF_CHARS];
for(int i=0;i<=size;i++){ // all variable of array is 0
for(int j=0;j<NO_OF_CHARS;j++){
TF[i][j] = 0;
}
}
for(int i=0;i<=size;i++){ // main algorithm
for(int j=0;j<NO_OF_CHARS;j++){
if(j==(int)pattern[i]){ // in the pattern characters,it put the index of indis
TF[i][j] = i+1;
}
else{
string a = pattern.substr(0,i); // to obtain part of pattern so to compare similarity ex ABCAB
a+=(char)j;
string a1= a.substr(0,a.size()-1); // get left part of pattern ex ABCA
string a2 = a.substr(1,a.size()); // get right part of pattern ex BCAB
// cout << a << endl;
// cout << a << " " << a1 << " " << a2 << endl;
string c1=a1; // to
string c2=a2;
// cout << "------------"<< endl;
for(int m=0;m<a1.size();m++){ // this loops to reduce part to pattern
// cout << c1 << " " << c2 << endl;
if(c1.compare(c2) == 0){ // if the right and left pattern is match, put the value at the index and exit from here;
// cout << "esit "<< i << " "<< j;
TF[i][j] = c1.size();
break;
}
c1 = a1.substr(0,a1.size()-m-1); // to reduce left pattern
c2 = a2.substr(m+1,a2.size()); // to reduce right pattern
}
}
}
}
}
void search(string pat, string txt,string patternCharacters)
{
int M = pat.size();
int N = txt.size();
int TF[M+1][NO_OF_CHARS];
createTable(pat, patternCharacters, TF); // create table for FSM
int i, state=0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i]];
if (state == M)
printf("Pattern found at index %d \n", i-M+1);
}
}
int main()
{
string pattern = "clear reflection";
string patternCharacters = "clearfction"; // each letter of pattern
string text = "AAAAAAAAAAAAAA";
search(pattern,text,patternCharacters);
return 0;
}