KMP算法

teach

关于KMP算法的next数组

KMP的next数组

一如既往先上代码：

1
2
3
4
5
6
7
8
9
void next()
{
   next[1]=0; next[2]=1; i=2; j=1; n=strlen(o);
   while(i<n)
   {
      if(j==0||o[i]==o[j]) {i++; j++; next[i]=j;}
      else j=next[j];
   }
}

说明

程序做到了两点:

  1. 寻找next数组
  2. 用KMP算法自调用

而只要稍加修改就可以用于判断最长字符串，代码如下

1
2
3
4
5
6
7
8
9
10
while (i < strlen(a) && j < strlen(user))
					{
						if (a[i] == user[j]) { i++; j++; continue; }
						else {
							if (j != 0) j = next[j];
							else { i++; j = 1; }
						}
					}
if (j >= strlen(user)) return i-strlen(user);
else return -1;