Knuth Morris Pratt

#include <bits/stdc++.h>
using namespace std;

int * plotKMP(string p)
{
    int * pi = new int[p.length()+1];
    pi[1] = 0;
    int k = 0;
    for(int q=2; q<=p.length(); q++){
        //Condition to reset the k to init
        while( k > 0 &&  p[k] != p[q-1] )
            k = pi[k];
        //If match is found, advance k(prefix length)
        if( p[k] == p[q-1] )
            k = k + 1;
        //Write prefix length to pi table
        pi[q] = k;

    }
    return pi;
}

void matchWithKMP(string text, string pattern){
    int n = text.length();
    int m = pattern.length();
    bool notFound = 1;
    int * pi = plotKMP(pattern);

    //Number of characters matched
    int q = 0;

    for(int i=1; i<=n; i++)
    {

        //Backtrack using pi table when match is not found
        while( q>0 && pattern[q] != text[i-1] )
            q = pi[q];

        //If match is found, advance q(next char is matched)
        if( pattern[q] == text[i-1] )
            q = q + 1;

        //If complete match is found:
        if( q==m )
        {
            notFound = 0;
            cout << "Pattern found with shift " << i-m << endl;
            //Backtrack to find next match
            q = pi[q];
        }

    }
    if(notFound)
        cout << "Not found" << endl;
}




int main(){
    string str1 = "xxxabcabcabcyyyabcabcabczzzabcabcabc";
    string str2 = "abcabcabc";

    int * x = plotKMP(str2);



    matchWithKMP(str1, str2);
}