Tuesday, February 26, 2013

string matching


void preMap(char *x,int m,int mpNext[])
{
int i,j;
i=0;
j=mpNext[0]=-1;
while(i<m)
{
while(j>-1 && x[i]!=x[j])
j=mpNext[j];
mpNext[++i]=++j;
}
}

void MP(char *x,int m,char* y,int n)
{
int i,j,mpNext[256];
preMap(x,m,mpNext);
i=j=0;
while(j<n)
{
while(i>-1 && x[i]!=y[j])
i=mpNext[i];
i++;
j++;
if(i>=m)
{
cout<<x<<endl;
i=mpNext[i];
}
}
}

No comments:

Post a Comment