////////////////////////////////////////////////
/**************KMP*****************************/
void GetNext(char *t,int next[])
{
int j=-1;
int i=0;
next[0]=-1;
while(i<strlen(t)-1)
{
if(j==-1 || t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int Kmp(char *s,char *t,int pos)
{
int i,j;
int len=strlen(t)+1;
int next[len];
GetNext(t,next);
i=pos;
j=0;
while(i<strlen(s) && j<strlen(t))
{
if((j==0) || (s[i]==t[j]))
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j>=strlen(t))
return i-strlen(t);
else
return -1;
}
////////////////////////////////////////////////////
由于做语言翻译机这道题，当时用了快排、二分搜索、和kmp。
其实后来发现，用hash表应该是最快的了。
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
