KMP (C++)

/*
** This is C++ implementation of KMP's pattern searcher.
** Runtime complexity: O(m+n)
*/

#include <cstdio>
#include <cstring>
 
void KMPSearch(char *pat, char *txt)
{
    int M=strlen(pat), N=strlen(txt), *LPS=new int[M];
 
    LPS[0]=0;
 
    for(int i=1,len=0;i<M;)
    {
        if(pat[i]==pat[len]) len++, LPS[i++]=len;
        else
        {
            if(len!=0) len=LPS[len-1];
            else LPS[i++]=0;
        }
    }

    for(int i=0,j=0;i<N;)
    {
        if(pat[j]==txt[i]) j++, i++;
 
        if(j==M)
        {
            printf("Found pattern at index %d\n", i-j);
            j=LPS[j-1];
        }
        else if(i<N && pat[j]!=txt[i])
        {
            if(j!=0) j=LPS[j-1];
            else i=i+1;
        }
    }
}
 
int main()
{
   char txt[]="AAAAABAAAAAAB", pat[]="AAAB";

   KMPSearch(pat, txt);

   return 0;
}