kmp算法?希尔排序算法?阮一峰kmp?KMP，深入讲解next数组的求解(2)

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

2.next数组的求解思路

通过上文完全可以对kmp算法的原理有个清晰的了解，那么下一步就是编程实现了，其中最重要的就是如何根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。我先给出我的代码：

P[],int next[]) 2 { m = strlen(P);next[(q = { k = next[k-(P[q] == P[k]) { 12 k++; 13 } 14 next[q] = k; 15 } 16 }

现在我着重讲解一下while循环所做的工作：

附代码：

1 #include

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

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