autometa

#include<iostream>
#include<string>
#include<vector>
#define Total_characters 256
using namespace std;

int ComputeNextState(string pattern, int curr_state, int max_state, int ch){
    if(pattern[curr_state]== ch and curr_state < max_state){
        return curr_state+1;
    }

    for(int new_state= curr_state; new_state>0; --new_state){
        if(pattern[new_state-1]==ch){
            int i;
            for(i=0; i<new_state-1; i++){
                if(pattern[i]!=pattern[curr_state-new_state+1+i])
                // if(pattern[new_state-2-i] != pattern[curr_state-1-i])
                    break;
            }
            if(i== new_state-1){
                return new_state;
            }
        }
    }
    return 0;
}
vector<vector<int>> ComputeTable(string pattern){
    int m= pattern.size();
    vector<vector<int>> ans(m+1, vector<int>(Total_characters));
    for(int i=0; i<=m; i++){
        for(int j=0; j<Total_characters; ++j){
            ans[i][j]= ComputeNextState(pattern, i, m, j);
        }
    }
    return ans;
}

void AutomataAlgorithm(string text, string pattern){
    int n= text.size();
    int m= pattern.size();

    vector<vector<int>> table= ComputeTable(pattern);
    int k=0;
    for(int i=0; i<n; i++){
        k= table[k][text[i]];
        if(k==m){
            cout<<"Pattern found with shift: "<<i-m+1<<endl;
        }
    }
}

int main(){
    string text, pattern;
    cout<<"Enter the Text: ";
    cin>>text;
    cout<<"Enter the Pattern: ";
    cin>>pattern;

    AutomataAlgorithm(text, pattern);

    return 0;
}