C++ 数据结构之kmp算法中的求Next()函数的算法

什么是KMP算法和Next()函数

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，能够解决的问题是，在一个文本串S中查找一个模式串P是否出现并且返回第一次出现的位置。而Next()函数则是在KMP算法中使用的一个关键的子函数，用于计算模式串P中每个前缀的最长相同真前缀和后缀的长度，从而实现快速的模式串匹配。

如何求Next()函数

设模式串P的长度为m，对于i=1,2,...,m，我们需要求出P[0:i-1]的最长相同真前缀和后缀的长度，即Next(i)的值。具体的算法如下：

1. 初始化Next(0)为-1，Next(1)为0。
2. 对于i=2,3,...,m-1，计算Next(i)。
3. 如果P[Next(i-1)]等于P[i-1]，则Next(i)等于Next(i-1)+1。
4. 否则，令j=Next(i-1)，不断向前递推Next(j)，例如，如果P[Next(j)]等于P[i-1]，则Next(i)等于Next(j)+1，否则继续递推。当递推到j=-1时，Next(i)等于0。

以上就是Next()函数的求解过程，该算法的时间复杂度为O(m)，其中m为模式串的长度。

两条示例说明

示例1

假设模式串P为“abababca”，则P的长度为8，对于i=2,3,...,7，我们依次计算Next(i)的值。

• i=2，P[0:1]="ab"，Next(1)=0。
• i=3，P[0:2]="aba"，Next(2)=0。
• i=4，P[0:3]="abab"，Next(3)=1。
• i=5，P[0:4]="ababa"，Next(4)=2。
• i=6，P[0:5]="ababab"，Next(5)=3。
• i=7，P[0:6]="abababc"，Next(6)=0。

因此，模式串P的Next()函数的值为Next={-1,0,0,1,2,3,0,1}。

示例2

假设模式串P为“abcabcabc”，则P的长度为9，对于i=2,3,...,8，我们依次计算Next(i)的值。

• i=2，P[0:1]="ab"，Next(1)=0。
• i=3，P[0:2]="abc"，Next(2)=0。
• i=4，P[0:3]="abca"，Next(3)=1。
• i=5，P[0:4]="abcab"，Next(4)=2。
• i=6，P[0:5]="abcabc"，Next(5)=3。
• i=7，P[0:6]="abcabca"，Next(6)=4。
• i=8，P[0:7]="abcabcab"，Next(7)=5。

因此，模式串P的Next()函数的值为Next={-1,0,0,1,2,3,4,5}。