KMP

KMP 算法可以线性时间在一个字符串中查找另一个字符串出现的情况。

具体的其实我不咋会说。。。直接放代码吧。

模板

P3375 【模板】KMP

求一个字符串在另一个字符串中出现的次数、位置等。实际上我代码写的求的是 border 数组 ( ) 。

其实就得稍微多写点，就比较容易记住了吧，也不是特别难理解。

我之前也稍微看过一下的，但是除了学了的时候写了点题，基本从来没用过。所以早就一点不记得了。

第一次 AC 这题是 24年11月2日，今天 25年3月28日。。但不同的是，现在我把很多东西记在这里，可以经常回到这里，甚至不小心点到一下，也能增加点映像？

vector<int> get_next(string s)
{
    vector<int> nxt(s.size());
    for (int i = 1; i < s.size(); i++)
    {
        int j = nxt[i - 1];
        while (j > 0 && s[j] != s[i])
            j = nxt[j - 1];
        nxt[i] = j;
        if (s[i] == s[j])
            nxt[i]++;
    }
    return nxt;
}
void ChatGptDeepSeek()
{
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> p = get_next(s2);
    int i = 0, j = 0;
    while (i < s1.size())
    {
        while (j > 0 && s1[i] != s2[j])
            j = p[j - 1];
        if (s1[i] == s2[j])
            i++, j++;
        else
            i++;
        if (j == s2.size())
        {
            cout << i - j + 1 << '\n';
            j = p[j - 1];
        }
    }
    for (auto x : p)
        cout << x << " ";
    cout << '\n';
}

[蓝桥杯 2024 国 B] 最长回文前后缀

也算只是随便找了一个可以用到 KMP 的题目，但需要一点额外的思维转换一下。

求最长回文前缀/后缀

并不是最长回文子串，回文子串一般得用别的方法求，貌似也是力扣典题，但是现在我应该不会。。

也是非常常用的方法，我就是从一个需要这个的题目，才来看 KMP 的。但是问的 GPT 怎么把 KMP 和回文串结合起来。

给一个字符串 \(s\) ，假设它的翻转的字符串是 \(s'\) ，那么我们求 $s+'?'+s' $ 的 border 数组，border数组的最后一个数字实际上就是最长回文前缀的长度。

ABC398F

可以转换成求最长回文后缀的问题，这一题里 Manacher 实现的也是同样的功能吗?没咋看这题的题解。。以后看 Manacher 的时候再回来看看这个题吧。

border next

我不太清楚，以下是 ChatGPT 的回答。我们数据结构书教的就是 next 数组，我上面写的都是 border 数组。

next 数组和 border 数组在字符串匹配算法中是相关但不完全相同的概念，具体来说，它们在 KMP（Knuth-Morris-Pratt）算法 中的作用有所区别。

---

1. border数组（前缀函数 π 数组）

在某些资料中，border 数组指的是 前缀函数，通常记作 π[i]，表示字符串 s[0...i] 的最长的相等真前后缀的长度。

定义：

令 π[i] 表示 s[0...i] 的最长相等真前后缀的长度：

• "真前缀" 指的是 s[0...k-1]，不能包含整个 s[0...i]
• "真后缀" 指的是 s[i-k+1...i]

示例：

对于字符串 s = "ababab"，其 border 数组（前缀函数 π）是：

i    0  1  2  3  4  5
s    a  b  a  b  a  b
π[i] 0  0  1  2  3  4

例如：

• s[0...4] = "ababa" 的最长相等真前后缀是 "aba"，长度为 3。

计算 π[i] 时，通常用递推公式：

• 如果 s[i] == s[π[i−1]]，那么 π[i] = π[i−1] + 1
• 否则，回溯到 π[π[i−1]−1]，直到找到匹配的前后缀或回溯至 0。

---

2. next 数组

next 数组常用于 KMP 算法，在不同的教材中定义可能略有不同：

• 一种定义：next[i] = π[i-1]（即 border 数组整体右移一位）
• 另一种定义（改进版）：next[i] 进一步优化，使得 next[i] 直接跳到正确的位置，不浪费多余的匹配尝试。

在 KMP 匹配过程中，next 数组用于在不匹配时快速跳转，例如：

• s[i] != p[j] 时，直接跳到 j = next[j]，而不是暴力回溯。

示例：

字符串 p = "ababab"，其 next 数组（取 next[i] = π[i-1]）：

i      0  1  2  3  4  5
p      a  b  a  b  a  b
π[i]   0  0  1  2  3  4
next[i] -1  0  0  1  2  3

（next[0] 通常设为 -1 方便实现 KMP）

---

3. 主要区别

概念	border 数组（前缀函数 π）	next 数组（部分匹配表）
定义	π[i] 是 s[0...i] 的最长相等真前后缀长度	next[i] = π[i-1] 或经过优化
作用	主要用于字符串分析	用于 KMP 失配时的跳转
计算公式	π[i] = π[i-1] + 1 或回溯	可能经过优化避免多余匹配
典型值	π[i] = {0, 0, 1, 2, ...}	next[i] = {-1, 0, 0, 1, 2, ...}

---

4. 总结

1. border 数组（前缀函数 π）是 s[0...i] 的最长相等真前后缀长度。
2. next 数组（部分匹配表）通常是 π 的变体，用于 KMP 算法加速失配跳转。
3. next 数组可能经过优化，避免一些不必要的回溯，使 KMP 更高效。

所以，它们本质上相关，但不是完全相同的东西！