KMP

线性时间匹配字符串的算法。

引入：前缀函数

先明确「前缀」和「后缀」的定义：

  • 前缀：从字符串开头开始的子串（如 abcde 的前缀有 a、ab、abc、abcd）；
  • 后缀：以字符串结尾结束的子串（如 abcde 的后缀有 e、de、cde、bcde）；
  • 「相等前缀和后缀」：指内容完全相同的前缀和后缀（如 abab 的前缀 ab 和后缀 ab 相等）。

则 π[i] 表示：

  • 子串 s[0…i]（即从第 0 个字符到第 i 个字符的子串）中，最长的、既等于该子串前缀，又等于该子串后缀的非平凡子串的长度。

注意最长这一条件。

计算前缀函数

因为有“最长”这一条件限制，因此采用 DP 即可实现其最优结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
s = "..."
pi[0] = 0;   // 没有子串
for(int i = 1; i < s.length(); ++i){
    int len = pi[i-1];    // s[0:i-1]最长前缀长度(作为已知量)
    if(s[len] == s[i]){
		// 如果下一个字符相同，则+1
        pi[i] = len + 1;
    }else{
        // 如果不同，那就要回退。如何回退？可以枚举len(最长前缀长度)！也就是：
        // 枚举x in len， s[0:x] == s[i-x-1:i-1] 并且 s[x+1] == s[i]
        // 画图！因为两个pi[i-1]区间内是相等的，可以得到对称性：s[0:x] == s[len-1-x:len-1]
        // 所以只需要令新的len = pi[x]且s[i] == s[len]即可得到pi[i]
        while(len >= 0 && s[i] != s[len]){
            len = pi[len-1];
        }
        pi[i] = len + 1;
    }
}

KMP

与 next 的关系

next 不是前缀函数本身，而是基于前缀函数构造的“跳转表”，用于在匹配失败时决定模式串该“回退到哪里”。

1
2
3
4
5
6
7
8
9
10
11
12
13
pat = "";  // 模式
str = ""; 
i = 0;     // str指针
j = -1;    // next 指针
next = pi; // 模式串前缀函数且next[0] == -1
while(i < str.length()){
    if(j == -1 || pat[i] == str[i]){
        ++i;++j;  // 如果在开头或有匹配的，那就都右移
    }else{
        j = next[j];  // 否则回退
    }
}

Manacher

寻找最长回文子串的算法。

寻找回文子串的一般做法

枚举一个中心点，并向两侧扩展，复杂度为$O(n^2)$。

不仅复杂度高，而且需要奇偶分类讨论。因此需要一个更高效的算法。

Manacher 算法

有一个字符串s="abcba"，为了使其有一个对称中心，我们可以考虑插入特殊字符使得其具有一个对称中心，也就是说 s.length() 从 $n$ 到 $2n+1$ 。

t = "^#a#b#c#b#a#$" 注意 ^$ 是防止越界的。

考虑有一个数组 P[i] 表示 s[i] 的半径(包括自身，例如ab的半径为1，aba的半径为2)。利用动态规划的思想，假设一切 P[i] 都是已知的，接下来寻找递推关系。显然有：

1
2
3
if(s[i+P[i]] == s[i-P[i]]){
    P[i]++;
}

同时有恒等式 s[i+P[i]-1] == s[i-P[i]+1]。

但是，如果仅仅这样，复杂度仍是 $O(n^2)$ ，其关键在于 P[i] 从 1 开始遍历。为了降低时间复杂度，我们需要通过一些观察使得 每次计算P前，都为P初始化一个值。

重要观察 ： 在中点 C 的半径内， P[i] 的最小值的分布是对称的，也就是说 P[C-k] == P[C+k] 当 k <= P[i] 且P均代表着可能的最小值。这由字符串对称性是显然的。因此，我们就可以根据这个最小值缩写枚举的范围。

需要注意的是，因为半径以外的内容是“不可见”的，因此先初始化的部分 (也就是对称点前的)有可能更大(因为半径外的字符串可能有影响)，这时就要求：对P的初始化不能使得p[i] > R-i也就是要使得该点为中心，半径不会超过右边界。

可以进行一步贪心：记录当前最大右边界 R 及最长回文中点 C 并维护之，有：

1
2
3
4
if(i + P[i] > R){
    C = i;
    R = i+P[i];
}

在半径内初始化P[i]：

1
2
3
4
if(i < R){
    // 如果在右边界内，那就用对称找到初始值，同时还要注意这个语句不能用来更新右边界，因此还要和 R-i 比较取小的一个
    P[i] = min(R-i, P[2*C-i]);
}

例题： LeetCode 647 回文子串：给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        vector<int> p(2333, 0);
        string t = "";
        for(auto ch: s){
            t = t + "#";
            t = t + ch;
        }
        t += "#";
        int r = 0;
        int c = 0;
        for(int i = 0; i < t.length(); ++i){
            if(i < r){
                p[i] = min(r-i, p[2*c-i]);
            }
            while(i-p[i] >= 0 && i+p[i] < t.length() && t[i+p[i]] == t[i-p[i]]){
                p[i]++;
            }
            if(i + p[i] > r){
                r = i+p[i];
                c = i;
            }
            res += p[i] / 2;
        }
        return res;
    }
};

Boyer-Moore