浅谈KMP模式匹配算法

写在前面
next数组
- 引理-1
- 优化的算法
匹配

写在前面

(kmp)模式匹配算法是一种能够在线性时间内判断字符串(A)是否是字符串(B)的子串的算法，并且优于哈希地，能够求出每个子串出现的位置。

我们一般称字符串(A)为模式串，字符串(B)为文本串。

next数组

(kmp)算法的核心步骤即为对模式串进行自我匹配求出(next)数组。

(next[i])表示以i结尾的非前缀子串与前缀能够匹配的最大长度，简单地说，就是模式串的前i位构成的子串的前缀后缀最大匹配长度，同时满足这个长度不等于i。比如对于某一个模式串(A="abababa")，当(i=6)时显然有如下两种可能的匹配：

[-~-~~~~~~~~~~~~~~~~~~~~~~\ |~a~~~b~~~a~~~b~~~a~~~b~|~a\ ~~~~~~~~~~~~~~~~--\ -~--~-~~~~~~~~~~~~\ |~a~~~b~~~a~~~b~~~a~~~b~|~a\ ~~~~~~--~-~-\ ]

所以得出(next[6]=4)。

朴素的算法复杂度显然为(O(n^2))，并不比暴力优秀。

因此考虑优化这个过程，首先证明如下引理：

引理-1

引理：如果(j)是(next[i])的一个可能取值，那么(next[j])为小于j的最大的(next[i])的可能取值。换言之，如果(j)不成立，那么可以直接跳过中间检查(next[j])。

证明：假设在([next[j],j])上存在一个(k)为(next[i])的可能取值，也就是说有(A[i-k+1sim i]=A[isim k])。因为(A[i-j+1sim i]=A[1sim j])，所以显然有(A[i-k+1sim i]=A[j-k+1sim j])（取后面一段），于是可以得出(A[1sim k]=A[j-k+1sim j])，那么说明(k)为成立并且比现在的(next[j])更优的值，显然矛盾！

因此推出结论，(next[j])为小于(j)的最大(next[i])可能取值。

优化的算法

回到原先的求next数组流程，既然我们有了引理-1，很容易想到每一次不能扩展的时候，都直接将j设为next[j]即可。

代码如下，不难证明这个算法有线性复杂度。

for (register int i=2,j=0; i<=n; ++i) {
    while (j&&s[i]!=s[j+1]) j=next[j];
    if (s[i]==s[j+1]) ++j;
    next[i]=j;
}

匹配

匹配的过程与求(next)数组相似，不难看出，当(j==A)的长度时即找到了匹配点。

代码如下：

for (register int i=1,j=0; i<=m; ++i) {
    while (j==n||(j&&s[j+1]!=t[i])) j=next[j];
    if (s[j+1]==t[i]) ++j;
    if (j==m) return i-m+1;
}