Friday, August 19, 2011

KMP algorithm for String Matching

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int pi[10000];
void prefix(char *p)
{
    int m=strlen(p);
    int k=0;
    pi[0]=0;
    for(int q=1;q<m;q++)
    {
        while(k>0 && p[k]!=p[q])
        {
            k=pi[k-1];
        }
        if(p[k]==p[q])
        {
            k++;
        }
        pi[q]=k;
    }
}
int main()
{
    int m;
    while(scanf("%d",&m)!=EOF)
    {
        char p[m];
        cin>>p;
        int q=0;
        prefix(p);
        char c;
        int flag=0;
        c=getchar();
        for(int i=0;;i++)
        {
            c=getchar();
            if(c=='\n')
            {
                if(i<m)
                {
                    cout<<"\n";
                    break;    
                }
                break;
            }
            while(q>0 && p[q]!=c)
            {
                q=pi[q-1];
            }
            if(p[q]==c)
                q++;
            if(q==m)
            {
                cout<<i-m+1<<endl;
                q=pi[q-1];
            }
        }
        if(flag)
            break;
    }
}

1 comment: