字符串算法--KMP

前言

字符串算法是OI、XCPC比赛中的一个常考考点。我在很久之前就学习过KMP，但最近才开始集中刷题，更深刻的理解KMP算法。

---

适用场景

字符串匹配

KMP算法可以以 $O(n + m)$ 的高效时间复杂度处理字符串匹配问题，即对于给定的文本串s和模式串p，KMP算法可以在线性时间复杂度内求解出s中每个p出现的位置。

找到循环部分

kMP算法的本质是求解nxt数组，即对于 $S$ 的每个前缀 $S_i$，nxt[i]为满足 $S_i$ 长度为x的前缀，等于长度为x的后缀的x的最大值。

通过nxt数组的性质，如果一个长度为n的字符串存在循环节（周期），那么它的循环节长度为：

$$len = n - nxt[n]$$

当len不整除n，或len与n相等时，这个字符串无周期。

求解两个字符串的最大重叠部分

对于字符串s和t，将两个字符串拼接在一起，以‘ ’隔开，(假设拼凑完的字符串长度为n)，nxt[n]即代表s长度为nxt[n]的前缀与t长度为nxt[n]的后缀长度相等。

算法原理

KMP算法的原理其实并不好解释。相比于暴力匹配字符串，nxt数组记录了字符串s每个前缀满足前缀与后缀相等的最大前后缀长度，即求解出了一个重叠部分，下次匹配时可以从nxt[j]处匹配，而不需要从头开始。

算法整体时间复杂度$O(n + m)$,其中n、m分别为文本串和模式串的长度。

我参考了ChatGPT-4o和OI-wiki，通过反复在vjudge的题单上刷题，终于理解了KMP的原理，nxt数组的深刻含义，可以着手解决复杂的KMP题。

代码（匹配问题）

void KMP(string s, string t) {
    int n = s.size(), m = t.size();
    s = " " + s;
    t = " " + t;
    // 求解nxt数组
    for(int i = 2, j = 0; i <= m; ++i) {
        whlie(j && t[i] != t[j + 1]) j = nxt[j];
        if(t[i] == t[j + 1]) ++j
        nxt[i] = j;
    }
    // 进行匹配
    for(int i = 1, j = 0; i <= n; ++i) {
        while(j && s[i] != t[j + 1]) j = nxt[j];
        if(s[i] == t[j + 1]) ++j;
        if(j == m) {	// 匹配成功
            cout << i - m + 1 << endl;
        }
    }
}

感想

kmp原理理解起来非常复杂，我找到的每一篇关于kmp算法的帖子下都有人评论看不懂。有许多dalao也用图文的方式解释kmp，但我最终还是先去背了算法的模板，在字符串题单中刷题，最后才逐渐掌握了kmp算法的原理及应用。