字符串

目录

• 字符串基础

• Hash / 哈希

• Trie / 字典树

• KMP

• Z 函数 / exKMP

• Manacher

---

字符串基础

• 一些概念

$\text{LCP}$(longest common prefix)：最长公共前缀。

$\text{LCS}$(longest common subsequence / substring)：最长公共子序列 / 子串。

$\text{LPS}$(longest palindromic sub…)：最长回文子串。

• 弱周期引理

如果一个字符串同时存在两个周期 $p$ 和 $q$，那么 $\text{gcd}(p,q)$ 也是一个周期（可以用类似辗转相除法的覆盖方法得到长度 $\text{gcd}(p,q)$）。

Hash / 哈希

（基础知识）

字符串中，我们可以让每一个字符串对应一个值，将所有串映射到一个较小的值域中，从而可以便捷地进行比较操作。

考虑一个多位数字的组成，有进制和位数两个关键元素。类似的，我们也可以设置能包含所有字符的进制，每位即是一个字符。

但这样的数字通常不小，我们可以再添加一个模数，将哈希值限制在一个可以接受的区间内。

比如说一个小写字母的字符串，我们可以将 $a$ 到 $z$ 分别对应到 $1$ 至 $26$，进制为 $114$，模数为 $514$：

abcd -> (1 * 114^3 + 2 * 114^2 + 3 * 114^1 + 4 * 114^0) % 514

• 以类似数的形式设置哈希值，可以让我们 $O(1)$ 直接计算字符串的结合 / 分割。

---

（哈希冲突）

显然，由于模的存在，存在两个字符串的哈希值相等的情况难以避免，我们将其称为哈希冲突。

好的进制 & 模数可以降低哈希冲突出现的概率：

• 一般选取质数，因为如果存在公因子，可能出现规律的哈希冲突。

• 模数要适当的增大，从而增大值域。

---

（多哈希）

更进一步，我们也可以设置多个映射函数。不同的字符串，对于两种映射方式，冲突的概率会大大降低。

（哈希表）

对于某个哈希值可能出现的冲突，我们可以直接将所有哈希值等于此的原串以链表的形式存储下来（当然，原串数量需要可接受），单次查询的复杂度接近 $O(1)$。

• $\text{STL}$ unordered_map 便是基于此实现的。

P3370 【模板】字符串哈希

U461211 字符串 Hash（数据加强）

---

CF1200E Compress Words

P4824 [USACO15FEB] Censoring S

P3498 [POI 2010] KOR-Beads

---

（可错配问题）

P4503 [CTSC2014] 企鹅 QQ

本题为一次错配，只需要逐一枚举可能的错配点判断即可。

对于 $k$ 次错配的问题，可以先选取两个要比较的字符串，二分从开始能匹配的最长距离，再暴力走错配点，复杂度 $O(m+kn\log m)$，其中 $n$ 为字符串数量，$m$ 为所有字符串总长。

---

Trie / 字典树

字符串相关

P8306 【模板】字典树

P4407 [JSOI2009] 电子字典

• $\text{Trie}$ 树浅层的大量合并使得实际复杂度降低。

$\text{01}$ 串相关

P4551 最长异或路径

CF1416C XOR Inverse

---

KMP

$\text{KMP}$ 算法可以通过线性预处理，解决字符串匹配的问题。

• $\text{border}$：一个子串即是前缀也是后缀。

如 abc*!@&%~abc
abc 就是原串的一个 border。

（如果你想在目标串上对模式串尝试匹配，可以在目标串前加一模式串，这样能匹配的位置就是一个 $\text{border}$。)

• $\text{next}$ 数组：对于当前选定字符串 $s$，最长的既是真前缀也是真后缀的子串长度，即小于 $|s|$ 的最长的 $\text{border}$ 长。

$\text{KMP}$ 的最直接目的是在线性的时间下处理出 $\text{next}$ 数组：

---

重要性质：下一个 $\text{next}$ 数组的值最多增加 1。

• 反证法：若 $\text{next}[i+1]-\text{next}[i]=a-b>1$，则在位置 $i+1$ 基础上两个 $\text{border}$ 同时在末端除去一个元素，可得 $i$ 处的一个 $\text{border}$ 长度为 $a-1(>b)$。

// s : 从 0 到 n - 1
for(int i = 1, j = 0; i < n; ++ i ){
    while(j && s[i] != s[j]) j = next[j];
    //通过不断失配尝试匹配。理解 next 数组的作用。
    if(s[i] == s[j]) ++j;
    //性质：下一个 next 数组值最多增加 1。
    next[i] = j;
}

// s : 从 1 到 n
for(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;
}

$\text{next}$ 数组也可以与树上问题产生联系。

P3375 【模板】KMP

---

P4391 [BalticOI 2009] Radio Transmission 无线传输

• 性质：如果存在 $\text{border}$，那么 $n-|\text{border}|$ 一定是原串的一个周期。

P3435 [POI 2006] OKR-Periods of Words

P4824 [USACO15FEB] Censoring S

P2375 [NOI2014] 动物园

---

P3426 [POI 2005] SZA-Template

• 极简 $\text{DP}$ 思路。（最高赞的题解）

考虑利用 $\text{border}$。如果某个串能至少覆盖前面 $n-next[i]$ 个字符，那么一定可以覆盖后面 $next[i]$ 个字符。于是设 $f[i]$ 为能够覆盖前缀长度 $i$ 的字符的最短答案。转移为 $f[j]=f[next[i]],i-j\leq next[i]$。

我个人会从感性的角度质疑为什么小的 $\text{border}$ 答案在中途不可行也不会掩盖大的 $\text{border}$，原因是此时大的 $\text{border}$ 只可能无法被小的 $\text{border}$ 覆盖，那么显然大 $\text{border}$ 向后延伸也不会用到小的 $\text{border}$。换句话说，如果短串能表示长串，那么长串一定不优，所以答案互不干涉。

---

• 树上思路。（引用来源的洛谷博客）

如果某个 $\text{border}$ 能够覆盖整个串，那么所有 $\text{border}$ 为其的位置的相邻距离不超过 $|\text{border}|$，表现到树上就是其所有子节点集合排列后，相邻位置距离不超过 $|\text{border}|$。

个人感觉可以通过启发式合并实现。

---

• 优秀的性质。（引用来源的洛谷博客）

定理：对于某字符串，其所有长度 $\geq n/2$ 的 $\text{border}$ 的长度是一个等差数列，且可以互相表示。

证明：设最大的 $\text{border}$ 长度为 $n-p$，那么 $p$ 是原串的一个周期。再选取一个 $\text{border}$ 长度为 $n-q$，那么 $q$ 是原串的一个周期。根据弱周期引理，$\text{gcd}(p,q)$ 也是原串的一个周期。

但我们已经钦定 $p$ 为最短的周期，所以 $\text{gcd}(p,q)=p$，从而 $p\mid q$。

不难发现，$kp$ 都是原串的周期，因此 $n-kp$ 都是原串的 $\text{border}$，等差数列是完整的。且 $|\text{border}|\geq n/2$ 时，小的 $\text{border}$ 可以表示大的 $\text{border}$。

---

据此，一个字符串的所有 $\text{border}$ 可以被划分为 $O(\log n)$ 个等差数列，每个数列末尾是对于该数列开头最长串的最小的长度大于 $len/2$ 的 $\text{border}$。

因此可能作为最终答案的 $\text{border}$ 的数量级为 $O(\log n)$，从小到大用哈希 + $\text{DP}$ 判断是否可覆盖。

---

Z 函数 / exKMP

与 $\text{KMP}$ 类似，我们所求的 $Z$ 函数 $z[i]$ 代表：字符串 $s$ 与其后缀 $s[i,n-1]$ 的最长公共前缀（$\text{LCP}$）的长度。

$\text{KMP}$ 与 $Z$ 函数的信息是相同的，只不过表现形式不同。

P5410 【模板】扩展 KMP / exKMP（Z 函数）

P7114 [NOIP2020] 字符串匹配

---

Manacher

P3805 【模板】Manacher