KMP
nxt[i]的意思是在str[i]前i个字符，即str[0]–str[i-1]的最长相同前后缀长度(非自身)，如abcdabc最长相同前后缀长度为3
直接代码
void Getnext(int next[],String t)
{
int j=0,k=-1;
next[0]=-1;
while(j<t.length-1)
{
if(k == -1 || t[j] == t[k])
{
j++;k++;
next[j] = k;
}
else k = next[k];
}
}
int KMP(String s,String t)
{
int next[MaxSize],i=0;j=0;
Getnext(t,next);
while(i<s.length&&j<t.length)
{
if(j==-1 || s[i]==t[j])
{
i++;
j++;
}
else j=next[j]; //j回退。。。
}
if(j>=t.length)
return (i-t.length); //匹配成功，返回子串的位置
else
return (-1); //没找到
}
