首页 > itarticle > Ming LiMing LiMing Li KMP算法 KMP的next数组

Ming LiMing LiMing Li KMP算法 KMP的next数组

admin 11月 13, 2020 0

关于KMP算法的next数组

一如既往先上代码：

void ()
{
   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];
   }
}

说明

程序做到了两点:

寻找next数组

用KMP算法自调用

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

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;