字符串练习笔记

一、字符串前置知识

注：若无特殊说明则默认字符串的下标从 $1$ 开始。

长度：$\vert s\vert$ 表示字符串 $s$ 的长度。

字符集：$\vert\Sigma\vert$ 表示字符集的大小，大多数字符串题只有小写字母 $\vert\Sigma\vert=26$。

模式串与文本串：从文本串中进行模式匹配寻找模式串。

子串：从原串中选取连续的一段字符串，空串也是子串。

前缀：$pre(s,k)$ 表示 $s$ 前 $k\ (0\le k\le\vert s\vert)$ 个字符构成的子串。

后缀：$suf(s,k)$ 表示 $s$ 后 $k\ (0\le k\le\vert s\vert)$ 个字符构成的子串。

最长公共前缀：$lcp(s,t)$ 表示 $s$ 和 $t$ 一样的最长的前缀。

最长公共后缀：$lcs(s,t)$ 表示 $s$ 和 $t$ 一样的最长的后缀。

注意任何子串都既是某个前缀的后缀也是某个后缀的前缀，子串、前缀、后缀都可以为 $s$ 可以为空串。

period：若 $0

border：若 $0

最长 border：$lb(s)$ 表示 $s$ 的最长的 border，若 $s$ 没有 border 则默认 $\vert lb(s)\vert=0$。

最长公共 border：$lcb(s,t)$ 表示 $s$ 和 $t$ 一样的最长的 border，若不存在则默认 $\vert lcb(s,t)\vert=0$。

注意 period 不能为 $\vert s\vert$ 不能为 $0$，border 不能为 $s$ 不能为空串。

border 的特殊性质：

1. 若 $pre(s,k)$ 是 $s$ 的 border，则 $\vert s\vert-k$ 是 $s$ 的 period。
2. 若 $k
3. 若 $k
4. 若 $s$ 是 $t$ 的 border，$t$ 是 $r$ 的 border，则 $s$ 是 $r$ 的 border。
5. 若 $s$ 是 $r$ 的 border，$t$ 是 $r$ 的 border，$\vert s\vert<\vert t\vert$，则 $s$ 是 $t$ 的 border。
6. $lb(s),lb(lb(s)),lb(lb(lb(s))),\cdots$ 构成了 $s$ 的所有 border，即 $s$ 的所有 border 环环相扣，由长到短被一条链串在了一起。

其中第 $1$ 条是 border 与 period 的关系，第 $2$ 条和第 $3$ 条为互逆命题，第 $4\sim 6$ 条是 border 的传递性。

这些特殊性质都非常简单，读者自证不难，举个栗子画个图就很容易证明。

二、kmp

设两个指针 $i$ 和 $j$ 表示当前文本串 $t$ 匹配到 $i$，模式串 $s$ 匹配到 $j$。

kmp 的核心思想为：找一个最大的 $j$ 满足 $suf(pre(t,i),j)=pre(s,j)$。

考虑 $i$ 由 $i-1$ 向右移动一位，若 $s[i]=t[i]$，则显然 $++j$ 即可。

但是若 $s[i]\not=t[i]$，则新的 $j'$ 与原先的 $j$ 一定满足 $j'

这是因为 $pre(s,j'-1)$ 显然是 $s$ 的前缀和 $pre(s,j)$ 的后缀，又因为 $j'

因此相当于找一个 $pre(s,j)$ 的最长的 border $pre(s,j'-1)$ 满足 $s[j']=t[i]$。

根据 border 的第 $6$ 条特殊性质，由长到短找到第一个满足 $s[j']=t[i]$ 的 border 即为最长的 border。

因为找的都是模式串 $s$ 的前缀的 border，与文本串 $t$ 无关，所以可以预处理 $nxt[j]$ 表示 $pre(s,j)$ 的最长的 border 的长度。

因此 kmp 的 next 函数的实质是：$nxt[j]=\vert lb(pre(s,j))\vert$，即 $s$ 的前缀的最长 border 的长度。

如何求 next 函数？设两个指针 $i$ 和 $j\ (j

根据 border 的第 $3$ 条特殊性质，若 $nxt[i-1]=j,\ s[i]=s[j+1]$，则 $nxt[i]=j+1$。

根据 border 的第 $6$ 条特殊性质，$pre(s,i-1)$ 的所有 border 是 $nxt[i-1],nxt[nxt[i-1]],nxt[nxt[nxt[i-1]]],\cdots$。

所以令 $j\leftarrow nxt[i-1]$ 开始看 $s[i]=s[j+1]$ 是否成立，不成立就令 $j\leftarrow nxt[j]$ 用 next 函数往回退，找出最长 border。

虽然 kmp 的预处理 next 函数过程和模式匹配过程都有进（$++j$）有退（$j\leftarrow nxt[j]$），但是由于每次进都是 $++j$，进的次数最多为 $\vert s\vert+\vert t\vert$，$j$ 非负，所以 $\Delta j\le2(\vert s\vert+\vert t\vert)$，因此摊还后总时间复杂度是线性的，为 $O(\vert s\vert+\vert t\vert)$。

• P3375 【模板】KMP字符串匹配

模板题，显然 $s1$ 是文本串，$s2$ 是模式串。

 1 const int N = 1e6 + 10;
 2 char s1[N], s2[N];
 3 int n, m, nxt[N];
 4 
 5 void build(const char *s)
 6 {
 7     nxt[1] = 0;
 8     for (int j = 0, i = 2; i <= n; ++i)
 9     {
10         while (j && s[i] != s[j + 1]) j = nxt[j];
11         if (s[i] == s[j + 1]) ++j;
12         nxt[i] = j;
13     }
14 }
15 
16 void match(const char *s, const char *t)
17 {
18     for (int j = 0, i = 1; i <= m; ++i)
19     {
20         while (j && t[i] != s[j + 1]) j = nxt[j];
21         if (t[i] == s[j + 1]) ++j;
22         if (j == n) cout << i - n + 1 << '\n';
23     }
24 }
25 
26 int main()
27 {
28     scanf("%s%s", s1 + 1, s2 + 1);
29     n = strlen(s2 + 1), m = strlen(s1 + 1);
30     build(s2); match(s2, s1);
31     for (int i = 1; i <= n; ++i) cout << nxt[i] << ' ';
32     return 0;
33 }

1