KMP算法（二）
总结一下： KMP算法的思想是：设s为主串，t为模式串设i为主串s当前比较字符的位置，j为模式串t当前比较字符串的位置，令i和j的初值0。当si=tj时，i和j分别增加1然后继续比较；否则i不变，j改变为等于next[j]再继续比较。以此类推，直到下列两种情况之一：(1)j退回到某个j=next[j]时有si=tj，则i和j分别增加1再继续比较；(2)j退回j=-1，此时令主串和模式串的位置各增1，再继续比较。这样的循环过程直到变量i大于等于主串s的长度或者变量j大于等于模式串t的长度的时候结束。
下面是算法的实现： 求子串的next[j]
void getNext(char *s, int next[])
{
int length = strlen(s);
int i = 0, k = -1;
next[0] = -1;
while (i < length)
{
if (k == -1 || s[i] == s[k])
{
i++;
k++;
next[i] = k;
}
else
{
k = next[k];
}
}
}KMP算法实现：
int KMPIndex(char *s, char *t, int next[])
{
int i = 0, j = 0, v;
int slen = strlen(s);
int tlen = strlen(t);
while (i < slen && j < tlen)
{
if (j == -1 || s[i] == t[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == tlen) v = i - tlen;
else v = -1;
return v;
}测试代码：
int main()
{
char *s = "abacabab";
char *t = "abab";
int next[5];
getNext(t, next);
for (int i = 0; i < 4; i++)
{
cout << next[i] << ' ';
}
cout << endl;
int index = KMPIndex(s, t, next);
cout << index << endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月16日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读