kmp算法视频?kmp算法java实现?KMP算法的next[]数组通俗解释(2)

//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推

while( Pattern[i] != Pattern[k]&&k!=0 )

k=prefix[k-1]; //继续递归

if( Pattern[i] == Pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++

prefix[i]=k+1;

else

prefix[i]=0; //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0

}

}

通过这个说明，估计能够理解KMP的next求法原理了，剩下的就很简单了。我自己也有点晕了，实在不喜欢那些数学公式，所以用形象逻辑思维方法总结了一下。

////////

KMP还有一种写法：这个写法是经过N个人优化的：

1 int j = -1, i = 0; 2 next[0] = -1; 3 while(i < len) 4 { 5 if(j == -1 || ss[i] == ss[j]) 6 { 7 8 i++; 9 j++; 10 next[i] = j; 11 } { 14 j = next[j]; 15 } 16 }

原文转自：

以上就是关于kmp算法的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-8677-2.html