#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;
}
}
Friday, August 19, 2011
KMP algorithm for String Matching
Subscribe to:
Post Comments (Atom)
Hey! Any problems with the emacs plugin? :P
ReplyDelete