简单字符串

字符串，就是由字符连接而成的序列。常见的字符串问题包括字符串匹配问题、子串相关问题、前缀/后缀相关问题、回文串相关问题、子序列相关问题等。具有很高的工程价值，比如搜索引擎。本文将介绍简单的字符串知识。

简单内容

这里是一些概念。

定义

一个字符集 $\Sigma$ 是一个建立了全序关系的集合，也就是说， $\Sigma$ 中的任意两个不同元素 $\alpha,\beta$ 都可以比较大小，其中的元素称之为字符。

一个字符串 $S$ 是将 $n$ 个字符顺次排列形成的序列， $n$ 表示字符串的长度，记为 $|S|$ 。字符的编号从 $0$ 开始（尽可能这样编号，这样是与标准一致的）。

字典序是以第 $i$ 个字符作为关键字符进行比较，特别注意，空字符是最小的："a" < "aa"。

子串、子序列、前缀后缀和回文串就不再赘述了。

char 数组

char s[1005]; // 声明字符数组
const char S[] = "abab"; // 常量字符数组

printf("%s", s); scanf("%s", s); // 读入和输出
sprintf(s, "%d ", a[i]); sscanf(s, "%d", &x); // 向字符串输出或从字符串读入

C++ string 类

#include <string>
std::string s;

string 对 char 数组兼容，上述内容都可以直接使用。除此之外，它还有许多特有内容。

string 很方便，但也很慢，遇到数据规模大的题应当慎重使用。

建议大家熟练掌握字符数组、string 和 sstream，都是很有用的。

字符串算法

字符串算法基本上都基于所求信息的特殊性质和已经求出的信息，类似于动态规划。

Trie 树

Trie，又称字典树或者前缀树，可以用来保存字符串的集合，是一种树形数据结构。

引入

一棵简单的 Trie

采用类似于树上前缀和的计算方式，可以得出 $2$ 号节点代表字符串 a， $6$ 号代表 aaa。

实现

实现时，我们一般把根节点记为 $0$ 号节点，因为它不代表任何字符串，每个节点有 ch[i][sigma_size]，其中 sigma_size 代表 Trie 树的字符集大小（不用 vector 之类的是为了保证时间效率，用空间换时间），表示是否有这个儿子。还有一个 val[i]，可以用于记录这个字符串的权值，比如记录这个节点是不是字符串。

模板，代码如下：

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, q, tot = 0;
int ch[3000005][62], val[3000005]; 

int f(char x) {
	if (x >= 'A' && x <= 'Z') return x - 'A';
	if (x >= 'a' && x <= 'z') return x - 'a' + 26;
	return x - '0' + 52;
}

void insert(char *s) {
	int x = 0, len = strlen(s);
	for (int i = 0; i < len; ++i) {
		int c = f(s[i]);
		if (!ch[x][c]) ch[x][c] = ++tot;
		x = ch[x][c];
		val[x] += 1;
	}
}

int find(char *s) {
	int x = 0, len = strlen(s);
	for (int i = 0; i < len; ++i) {
		int c = f(s[i]);
		if (!ch[x][c]) return 0;
		x = ch[x][c];
	}
	return val[x];
}

char s[3000005];
void solve(void) {
	scanf("%d%d", &n, &q);	
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j < 62; ++j)
			ch[i][j] = 0;
		val[i] = 0;
	}
	while (n--) {
		scanf("%s", s);
		insert(s);
	}
	while (q--) {
		scanf("%s", s);
		printf("%d\n", find(s));
	}
}

int main(void) {
	int T; scanf("%d", &T);
	while (T--) solve();
	return 0;
}

字符串 Hash

我们可以将一个字符串通过一个函数 $f$ 映射为一个整数。

实现

我们通常这样定义 Hash 函数： $f(s) = \sum_{i=0}^{l-1} s[i] \times b^{l-i} \pmod M$ 。有的时候是反过来的： $f(s) = \sum_{i=0}^{l-1} s[i] \times b^{i-1} \pmod M$ 。不过相比之下，前者更为常用。其中的 $b$ 可以根据心情决定其值。

模板，代码如下：

查看代码

#include <bits/stdc++.h>
#define LL long long

using namespace std;

int n, ans = 0;
vector <string> v[23333];

void calc(const string &s) {
    LL hash = 0;
    for (int i = s.length() - 1; i >= 0; --i)
        hash = (hash * 130 + s[i]) % 233;
    for (int i = 0; i < v[hash].size(); ++i)
        if (v[hash][i] == s) return;
    v[hash].push_back(s);
    ++ans;
}

int main(void) {
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        calc(s);
    }
    cout << ans << endl;
    return 0;
}

上述代码采用了拉链法实现，效率相对来说比较低下，现在我们来介绍一种更为常用的方法：

我们采用两个模数做两次 Hash，如果 Hash 值都相同才判定它们是相同的。两个字符串 Hash 相同的概率本身就很小，双模数之后更小，因此几乎不会出错。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MOD1 = 998244853;
const int MOD2 = 1011000007;

i64 H1(const string &s) {
    i64 hash = 0;
    for (int i = s.length() - 1; i >= 0; --i)
        hash = (hash * 233 + s[i]) % MOD1;
    return hash;
}
i64 H2(const string &s) {
    i64 hash = 0;
    for (int i = s.length() - 1; i >= 0; --i)
        hash = (hash * 233 + s[i]) % MOD2;
    return hash;
}

pair<i64, i64> a[10005];

int main(void) {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    string s;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        a[i] = make_pair(H1(s), H2(s));
    }
    sort(a + 1, a + n + 1);
    int ans = 1;
    for (int i = 2; i <= n; ++i)
        if (a[i].first != a[i - 1].first && a[i].second != a[i - 1].second) ++ans;
    printf("%d\n", ans);
    return 0;
}

子串 Hash

当哈希函数这样定义时： $f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$ 。我们可以采用类似于前缀和的方式来快速求解子串的哈希（从 $1$ 开始编号）。

令 $f_j(s)$ 代表 $f(s[1\dots j])$ ，那么有 $f_j(s)=\sum_{i=1}^{j} s[i] \times b^{r-i} \pmod M$ ，而 $f(s[l\dots r])=s[l]\times b^{r-l}+\cdots+s[r]$ ，进而有 $f(s[l\dots r])=f_r(s)-f_{l-1}(s)\times b^{r-l+1}$ 。

Hash 的应用

字符串哈希能解决很多问题。

字符串匹配

求出模式串的哈希值，然后查找每一个字串的哈希值，比较是否相等。

允许失配的字符串匹配

比如说允许失配 $k$ 次。这个问题可以使用 Hash + 二分来解决，设当前枚举的子串为 $s'$ ，可以二分出 $s'$ 第一个与模式串不同的地方，然后将这个失配的位置以前的内容删去，再查找下一个失配的位置。时间复杂度为 $O(kn\log m)$ 。

最长回文子串

记 $R_i$ 代表以 $i$ 结尾的最长回文长度。由于 $R_i\le R_{i-1}+2$ ，因此我们只需要从 $R_{i-1}+2$ 的长度开始递减，找到第一个回文串即可，时间复杂度为 $O(n)$ 。

Manacher 算法

它可以高效解决回文问题。

概述

Manacher 仅能找到长度为奇数的回文串，因此在它工作前，我们要在它的每个字符间都插入一个相同的分割符。同时还要在字符串前后插入一对不同的字符防止越界。

设以 $s_i$ 为对称中心的回文串中最长的回文半径（以 $i$ 为对称中心，回文串的长度为奇数，半径是指从对称中心到一段的字符串长度）为 $p_i$ 。那么如果 $x$ 是 $i$ 的回文半径，则 $0\sim x$ 都是。

Manacher 会记录在遍历过的 $1\sim i-1$ 中，以任意一点为对称中心的回文串最大右端点 $r$ ，并记录此时的对称中心 $d$ 。若当前 $i>r$ ，则让 $p_i=1$ 直接开算；否则将 $p_i$ 先赋值成 $\min\{p_{2d-i},r-i+1\}$ 再尝试更新。因为 $2d-i$ 与 $i$ 关于 $d$ 对称，因此在 $[d-r+1,d+r-1]$ 内，以 $2d-i$ 为对称中心的回文串也是以 $i$ 为对称中心的回文串。当 $p_{2d-i}<r-i+1$ 时， $p_i$ 已经最大（否则 $p_{2d-i}$ 也可以更大）；否则 $p_i$ 被初始化为 $r-i+1$ （不能超过 $d$ 的势力范围，因为这个对称性尽在 $[d-r+1,d+r-1]$ 内生效，需要满足 $i+p_i-1\le r$ ）。由于每次扩展都会使 $r$ 变大，故均摊时间复杂度为 $O(n)$ 。

模板，代码如下：

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int m, n, p[22000010];
char s[22000010], t[11000005];

int main(void) {
    scanf("%s", t + 1); m = strlen(t + 1);
    s[0] = '#'; s[n = 1] = '@';
    for (int i = 1; i <= m; ++i) s[++n] = t[i], s[++n] = '@';
    s[n + 1] = '!'; 
    int ans = 0;
    for (int i = 1, r = 0, d = 0; i <= n; ++i) {
        if (i > r) p[i] = 1; else p[i] = min(r - i + 1, p[2 * d - i]);
        while (s[i - p[i]] == s[i + p[i]]) ++p[i];
        if (i + p[i] - 1 > r) d = i, r = i + p[i] - 1;
        ans = max(ans, p[i] - 1);
    }
    printf("%d\n", ans);
    return 0;
}

应用

我们戏称 Manacher 算法为马拉车，它可以求出以某个字符开头或结尾的最长回文子串。

以固定结尾为例。考虑每一个位置 $i$ ，若我们更新了 $r$ ，那么在更新 $r$ 前要对 $[r+1,i+p_i-1]$ 的答案更新为 $j-i+1$ （ $j$ 不是分隔符的时候进行）。

均摊之后时间复杂度依然为 $O(n)$ 。

[国家集训队]最长双回文串。我们正反跑两边 Manacher，找出以某个字符开始或结束的最长回文串。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int m, n, p[200010];
int L[100010], R[100010];
char t[100005], s[200010];

int P(int x) {
    if (x >= 1 && x <= n) return p[x];
    return 0;
}

int main(void) {
    scanf("%s", t + 1); m = strlen(t + 1);
    s[0] = '#'; s[n = 1] = '@';
    for (int i = 1; i <= m; ++i) s[++n] = t[i], s[++n] = '@';
    s[n + 1] = '!';
    for (int i = 1, d = 0, r = 0; i <= n; ++i) {
        if (i > r) p[i] = 1; else p[i] = min(r - i + 1, P(2 * d - i));
        while (s[i + p[i]] == s[i - p[i]]) ++p[i];
        if (i + p[i] - 1 > r) {
            for (int j = r + 1; j <= i + p[i] - 1; ++j)
                if (j % 2 == 0) R[j / 2] = j - i + 1;
            d = i, r = i + p[i] - 1;
        }
    }
    for (int i = n, d = 0, r = n; i >= 1; --i) {
        if (i < r) p[i] = 1; else p[i] = min(i - r + 1, P(2 * d - i));
        while (s[i + p[i]] == s[i - p[i]]) ++p[i];
        if (i - p[i] + 1 < r) {
            for (int j = r - 1; j >= i - p[i] + 1; --j)
                if (j % 2 == 0) L[j / 2] = i - j + 1;
            d = i, r = i - p[i] + 1;
        }
    }
    int ans = 0;
    for (int i = 1; i < m; ++i)
        if (R[i] && L[i + 1]) ans = max(ans, R[i] + L[i + 1]);
    printf("%d\n", ans);
    return 0;
}

KMP 模式匹配

虽然说这是个基础算法，但是思想非常棒。

KMP 算法能够在线性时间内判定一个字符串在另一个字符串中所有出现位置，而且为我们提供了一些非常有用的附加信息。

概述

模板。

现在我们要对字符串 $A$ 计算其在 $B$ 中的出现位置，过程分为两步：

对 $A$ 自己进行匹配，求出 $nxt$ 数组， $nxt[i]$ 代表 A 中以 $i$ 结尾的非前缀子串与 A 的前缀能够匹配的最大长度，也就是说 $nxt[i]=\max\{j\mid j<i,A[i-j+1\sim i]=A[1\sim j]\}$ ，如果不存在则 $nxt[i]=0$ 。
对 $A$ 和 $B$ 进行匹配，求出数组 $f$ ， $f[i]$ 代表 $B$ 中以 $i$ 结尾的子串与 $A$ 的前缀能够匹配的最大长度。

这两步的实现方式几乎一样，我们以第 $1$ 步为例子。

根据定义， $nxt[1]=0$ ，接下来我们扫描字符串依次计算 $nxt$ 。假定 $nxt[1\sim i-1]$ 已经计算完毕，记 $p$ 为当前扩展的长度，并尝试继续扩展。如果扩展失败，那么令 $p=nxt[p]$ ，直到 $p$ 变为 $0$ 。如果能够匹配成功， $p$ 就加一，此时 $nxt[i]$ 就为 $p$ 。

均摊时间复杂度为 $O(n+m)$ ，这里不作证明^[1]。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, m, nxt[1000005], f[1000005];
char s1[1000005], s2[1000005];

int main(void) {
    scanf("%s%s", s1 + 1, s2 + 1);
    n = strlen(s1 + 1), m = strlen(s2 + 1);
    for (int i = 2, p = 0; i <= m; ++i) {
        while (p && s2[i] != s2[p + 1]) p = nxt[p]; // 扩展失败
        if (s2[i] == s2[p + 1]) ++p; // 尝试扩展匹配长度
        nxt[i] = p;
    }
    for (int i = 1, p = 0; i <= n; ++i) {
        while (p && s1[i] != s2[p + 1]) p = nxt[p];
        if (s1[i] == s2[p + 1]) ++p;
        f[i] = p;
        if (f[i] == m) printf("%d\n", i - m + 1);
    }
    for (int i = 1; i <= m; ++i)
        printf("%d ", nxt[i]);
    putchar('\n');
    return 0;
}

Border 理论

定义长度为 $n$ 的字符串 $s$ 的 $\text{Border}(s)$ 表示 $s$ 所有相等的真前缀后缀集合。也就是说，如果一个字符串是 Border，那么它同时是 $s$ 的前缀和后缀。而 $s$ 中最长的一个 Border 就是 $nxt[n]$ 。

如果说 $p$ 是 $s$ 的周期，那么 $s_i=s_{i+p}(1\le i\le n-p)$ 。

Border 拥有以下性质：

若 $p$ 为 $s$ 的周期，则 $s[1\dots n-p]$ 为 $s$ 的 Border。由周期的定义即可证明。
如果 $s$ 存在 Border，那么最短的长度不超过字符串的一半。
字符串 $s$ 的最小周期为 $|S| - nxt[|S|]$ 。

失配树

如果我们从 $nxt[i]$ 向 $i$ 连边，那么我们会得到一棵以 $1$ 为根的有根树，这就是失配树。

失配树具有一个很好的性质：对于树上任意两个具有祖先后代关系的节点 $x,y$ ， $s[1\dots x]$ 是 $s[1\dots y]$ 的 Border。因此要查询两个前缀字符串的最长公共 Border，只需要查找两个点在失配树上的 LCA 即可（由于 Border 不能是自己，因此不要特判 $x=y$ ）。

模板，代码如下：

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, m, f[20][1000005], dep[1000005];
char s[1000005];

int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; i >= 0; --i)
        if (dep[f[i][x]] >= dep[y]) x = f[i][x];
    for (int i = 19; i >= 0; --i)
        if (f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
    return f[0][x];
}

int main(void) {
    scanf("%s%d", s + 1, &m); n = strlen(s + 1); dep[1] = 1;
    for (int i = 2, p = 0; i <= n; ++i) {
        while (p && s[i] != s[p + 1]) p = f[0][p];
        if (s[i] == s[p + 1]) ++p;
        dep[i] = dep[f[0][i] = p] + 1;
    } 
    for (int i = 1; i <= 19; ++i)
        for (int j = 1; j <= n; ++j)
            f[i][j] = f[i - 1][f[i - 1][j]];
    while (m--) {
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", LCA(x, y));
    }
    return 0;
}

Z 函数

后缀数组

Problemset

字符串的题很多，也很有趣。

Trie

Trie 树看起来很简单，但真的很有用。

[TJOI2010] 阅读理解

Portal.

空间限制很紧张，那么就对询问建立 Trie，然后依次检索文章，最后统一输出答案。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <set>

using namespace std;

int n, m;
int ch[200005][26], tot = 0;
string tmp;
vector<string> a[1005];
vector<int> ret[200005];
set<int> ans[100005];

void insert(int p) {
    cin >> tmp;
    int x = 0;
    for (int i = 0; i < tmp.length(); ++i) {
        int c = tmp[i] - 'a';
        if (!ch[x][c]) ch[x][c] = ++tot;
        x = ch[x][c];
    }
    ret[x].emplace_back(p);
}

void check(int p, int y) {
    int x = 0;
    string &s = a[p][y];
    for (int i = 0; i < s.length(); ++i) {
        int c = s[i] - 'a';
        if (!ch[x][c]) return;
        x = ch[x][c];
    }
    for (int i = 0; i < ret[x].size(); ++i)
        ans[ret[x][i]].insert(p);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int l; scanf("%d", &l);
        while (l--) {
            cin >> tmp;
            a[i].push_back(tmp);
        }
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
        insert(i);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < a[i].size(); ++j)
            check(i, j);
    for (int i = 1; i <= m; ++i) {
        for (int x : ans[i])
            printf("%d ", x);
        putchar('\n');
    }
    return 0;
}

[USACO08DEC] Secret Message G

Portal.

直接建 Trie 统计即可，注意不要算重。

查看代码

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int m, n;
int ch[500005][2], tot = 0;
int s[500005], e[500005];

int main(void) {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; ++i) {
        int len, x = 0; scanf("%d", &len);
        for (int j = 0; j < len; ++j) {
            int c; scanf("%d", &c);
            if (!ch[x][c]) ch[x][c] = ++tot;
            x = ch[x][c];
            ++s[x];
        }
        ++e[x];
    }
    for (int i = 1; i <= n; ++i) {
        int len, x = 0, ans = 0; scanf("%d", &len);
        bool flag = false;
        for (int j = 0; j < len; ++j) {
            int c; scanf("%d", &c);
            if (flag) continue;
            if (!ch[x][c]) flag = true;
            x = ch[x][c];
            ans += e[x];
        }
        if (!flag) ans += s[x] - e[x];
        printf("%d\n", ans);
    }
    return 0;
}

[USACO12DEC] First! G

Portal.

有 $n$ 个仅有小写字母构成的字符串，你可以任意改变字符的顺序（比如规定 b 比 a 小），问哪些字符串可以通过这种方式变成字典序最小的字符串。

想一想，字典序的比较是从前到后的。首先如果一个字符串是另一个的前缀，那么不作为前缀的那个一定不可以。这样以来，我们建立 Trie 树，在 Trie 上同一父亲，同一层的节点会进行字典序比较，我们只需要给这些字符连一条有向边，代表大小关系，最后会得到一张图。改变的字符顺序就是这个图的拓扑序。如果这个图不是 DAG，那么这个字符串不能作为答案。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int n;
int ch[300005][26], tot = 0;
bool e[300005], is_ans[30005];
string s[30005];

void insert(int p) {
    int x = 0;
    cin >> s[p];
    for (int i = 0; i < s[p].length(); ++i) {
        int c = s[p][i] - 'a';
        if (!ch[x][c]) ch[x][c] = ++tot;
        x = ch[x][c];
    }
    e[x] = true;
}

int in[30];
bool G[30][30];

void Kahn(void) {
    queue<int> q;
    for (int i = 0; i < 26; ++i)
        if (in[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < 26; ++v)
            if (G[u][v]) {
                --in[v];
                if (in[v] == 0) q.push(v);
            }
    }
}

bool check(int p) {
    string &t = s[p];
    int x = 0;
    memset(G, 0, sizeof(G));
    memset(in, 0, sizeof(in));
    for (int i = 0; i < t.length(); ++i) {
        if (e[x]) return false;
        int c = t[i] - 'a';
        for (int j = 0; j < 26; ++j)
            if (c != j && ch[x][j] && !G[c][j]) {
                G[c][j] = true; // o->m m->o
                ++in[j];
            }
        x = ch[x][c];
    }
    Kahn();
    for (int i = 0; i < 26; ++i)
        if (in[i]) return false;
    return true;
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) insert(i);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (check(i)) {
            ++ans;
            is_ans[i] = true;
        }
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i)
        if (is_ans[i]) cout << s[i] << '\n';
    return 0;
}

[SCOI2016] 背单词

Portal.

一共要学习 $n$ 个单词，可以自行决定学习单词的顺序，学习第 $x$ 个单词要吃的铁轨数量是：

如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 $n \times n$ 个铁轨才能学会；
当它的所有后缀都被填入表内的情况下，如果在 $1 \cdots x-1$ 的位置上的单词都不是它的后缀，那么他吃 $x$ 个铁轨就能记住它；
当它的所有后缀都被填入表内的情况下，如果 $1 \cdots x-1$ 的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 $y$ ，那么他只要吃 $x-y$ 个铁轨就能把它记住。

后缀相同可以转化为前缀相同（可以翻转字符串，也可以反着建 Trie）， $1$ 决策显然是不优的，利用它省操作怎么都省不下来，而且不存在两个单词互为前缀，所以 $1$ 决策一定可以避免。

$2$ 的话其实是 $3$ 中 $y=0$ 的情况。也就是说，我们可以当作只有 $3$ 操作。

建立好 Trie 树后，为了防止 $1$ 操作的出现，我们一定要按照 DFS 序进行遍历（其它方式并不优）。由于非字符串的节点是没有贡献的，所以我们可以把它们去掉，将剩下的点作为导出子树进行 DFS 序遍历，而且是越重的越靠后遍历。为什么？采用微扰法来证明贪心，一个重的子树和轻的子树交换遍历顺序，那么只有重的子树的根节点的代价和轻的子树的根节点代价会改变，交换前代价是轻子树的大小，交换后代价是重子树的大小，因此不交换更优。

为什么要按照 DFS 序进行遍历？同样可以使用微扰法来证明，可以发现任意交换两个之后它们的贡献都会变大（距离父亲的遍历序号更远了，吃的铁轨数量更多了），因此一定不优。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long i64;

i64 ans = 0;
int n, ch[510005][26], tot = 0, cnt = 0;
int siz[500005], dfn[500005], lst[500005];
char s[500005];
bool e[510005];
vector<int> G[500005];

bool cmp(int x, int y) {
    return siz[x] < siz[y];
}

void dfs(int x) {
    if (e[x]) G[lst[x]].emplace_back(x), lst[x] = x;
    for (int i = 0; i < 26; ++i)
        if (ch[x][i]) lst[ch[x][i]] = lst[x], dfs(ch[x][i]);
}

void dfs2(int x, int fa) {
    siz[x] = 1;
    for (int y : G[x]) {
        dfs2(y, x);
        siz[x] += siz[y];
    }
    sort(G[x].begin(), G[x].end(), cmp);
}

void dfs3(int x, int fa) {
    dfn[x] = ++cnt; ans += dfn[x] - dfn[fa];
    for (int y : G[x]) dfs3(y, x);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s);
        reverse(s, s + strlen(s));
        int x = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - 'a';
            if (!ch[x][c]) ch[x][c] = ++tot;
            x = ch[x][c];
        }
        e[x] = true;
    }
    dfs(0);
    dfs2(0, 0);
    dfs3(0, 0);
    printf("%lld\n", ans);
    return 0;
}

[JSOI2009] 电子词典

Portal.

有 $n(n\le 10^4)$ 个单词的词典和 $m(m\le 10^4)$ 次询问，每次询问词典中有多少个单词与查询的单词可以模糊匹配（指可以通过一次修改、删除或添加字符变成一样的字符串），如果本来就有这个单词则输出 -1。保证 $|s|\le 20$ 。

对词典构建 Trie 树，对于每个询问则直接使用 DFS 暴力查找，记录一个 flag 表示是否编辑过即可。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

int n, m, len, ans;
int ch[200000][26], tot = 0;
char s[25];
bool e[200000], vis[200000], is_word;
set<int> S;

void dfs(int x, int p, bool flag) {
    if (p == len && e[x]) {
        if (!flag) is_word = true;
        else S.insert(x);
        return;
    }
    int c = s[p] - 'a';
    if (ch[x][c]) dfs(ch[x][c], p + 1, flag); // 正常写
    if (!flag) {
        if (p < len) dfs(x, p + 1, true); // 删除
        for (int i = 0; i < 26; ++i)
            if (ch[x][i]) {
                dfs(ch[x][i], p, true); // 添加
                if (p < len && i != c) dfs(ch[x][i], p + 1, true); // 修改
            }
    }
}

int main(void) {
    scanf("%d%d", &n, &m);
    while (n--) {
        scanf("%s", s);
        int x = 0, len = strlen(s);
        for (int i = 0; i < len; ++i) {
            int c = s[i] - 'a';
            if (!ch[x][c]) ch[x][c] = ++tot;
            x = ch[x][c];
        }
        e[x] = true;
    }
    while (m--) {
        is_word = false; ans = 0;
        scanf("%s", s); len = strlen(s);
        S.clear();
        dfs(0, 0, 0);
        if (is_word) puts("-1");
        else printf("%d\n", S.size());
    }
    return 0;
}

字符串 Hash

Hash 算法很简单，可以完成许多需要高级算法才能完成的任务。

[NOI Online 2021 提高组] 积木小赛

Portal.

我们枚举 Bob 字符串，看是否能匹配，并计算其 Hash 值，然后去重就是答案。这不是正解，需要吸氧。

查看代码

#include <cstdio>
#include <algorithm>

using namespace std;
typedef unsigned long long u64;

int n, tot = 0;
char a[3010], b[3010];
u64 t[9000005];

int main(void) {
    scanf("%d", &n); fgets_unlocked(a + 1, 5, stdin);
    fgets_unlocked(a + 1, 3002, stdin);
    fgets_unlocked(b + 1, 3002, stdin);
    for (int i = 1; i <= n; ++i) {
        u64 v = 0; int p = 1;
        for (int j = i; j <= n; ++j) {
            while (p <= n && a[p] != b[j]) ++p;
            if (p > n) break; ++p;
            v = v * 233 + b[j];
            t[++tot] = v;
        }
    }
    sort(t + 1, t + tot + 1);
    int ans = 1;
    for (int i = 2; i <= tot; ++i)
        if (t[i] != t[i - 1]) ++ans;
    printf("%d\n", ans);
    return 0;
}

[CF1200E] Compress Words

Portal.

使用字符串哈希求出最长的相等前后缀。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int B1 = 233, B2 = 479;
const int M1 = 957657979, M2 = 996987653;

int n, m, l, b1[1000005], b2[1000005];
char s[100005], ans[1000005];
int ash1[1000005], ash2[1000005];

int main(void) {
    int n; scanf("%d", &n);
    b1[0] = b2[0] = 1;
    for (int i = 1; i <= 1000000; ++i) b1[i] = 1ll * b1[i - 1] * B1 % M1;
    for (int i = 1; i <= 1000000; ++i) b2[i] = 1ll * b2[i - 1] * B2 % M2;
    for (int op = 1; op <= n; ++op) {
        scanf("%s", s + 1); m = strlen(s + 1);
        int h1 = 0, h2 = 0, len = 0;
        for (int i = 1; i <= m && i <= l; ++i) {
            h1 = (1ll * h1 * B1 + s[i]) % M1;
            h2 = (1ll * h2 * B2 + s[i]) % M2;
            if (ash1[l] == (h1 + 1ll * ash1[l - i] * b1[i]) % M1 &&
                ash2[l] == (h2 + 1ll * ash2[l - i] * b2[i]) % M2) 
                len = i;
        }
        for (int i = len + 1; i <= m; ++i) {
            ans[++l] = s[i];
            ash1[l] = (1ll * ash1[l - 1] * B1 + s[i]) % M1;
            ash2[l] = (1ll * ash2[l - 1] * B2 + s[i]) % M2;
        }
    }
    printf("%s\n", ans + 1);
    return 0;
}

Manacher 算法

就是回文。

[国家集训队] 拉拉队排练

Portal.

直接 Manacher，利用前缀和统计不同长度的回文串即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
const int MOD = 19930726;

int n, p[1000005], cnt[1000005];
i64 k;
char s[1000005];

int poww(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) res = 1ll * res * a % MOD;
    return res;
}

int main(void) {
    scanf("%d%lld%s", &n, &k, s + 1); s[0] = '$', s[n + 1] = '%';
    for (int i = 1, r = 0, d = 0; i <= n; ++i) {
        if (i > r) p[i] = 1; else p[i] = min(r - i + 1, p[2 * d - i]);
        while (s[i - p[i]] == s[i + p[i]]) ++p[i];
        if (i + p[i] - 1 > r) d = i, r = i + p[i] - 1;
        ++cnt[p[i]];
    }
    int ans = 1;
    for (int i = (n + 1) / 2; i >= 1 && k > 0; --i) {
        cnt[i] += cnt[i + 1];
        ans = 1ll * ans * poww(i * 2 - 1, min(k, (i64)cnt[i])) % MOD;
        k -= cnt[i];
    }
    if (k > 0) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

[UVA11475] Extend to Palindrome

Portal.

用 Manacher 求出第一个可以扩展到结尾的子串，然后根据它扩展即可。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long i64;
const int MOD = 19930726;

int n, p[1000005];
char t[1000005], s[2000005];

int main(void) {
    while (scanf("%s", t + 1) == 1) {
        s[0] = '$'; s[n = 1] = '@';
        int m = strlen(t + 1), pos;
        for (int i = 1; i <= m; ++i) s[++n] = t[i], s[++n] = '@';
        s[n + 1] = '%';
        for (int i = 1, d = 0, r = 0; i <= n; ++i) {
            if (i > r) p[i] = 1; else p[i] = min(r - i + 1, p[2 * d - i]);
            while (s[i - p[i]] == s[i + p[i]]) ++p[i];
            if (i + p[i] - 1 > r) d = i, r = i + p[i] - 1;
            if (i + p[i] - 1 == n) {
                pos = (i - p[i] + 1) / 2;
                break;
            }
        }
        printf("%s", t + 1);
        for (int i = pos; i >= 1; --i)
            putchar(t[i]);
        putchar('\n');
    }
    return 0;
}

[THUPC2018] 绿绿和串串

Portal.

绿绿有一个由小写字母组成的非空字符串 $R$ ，但 Yazid 不知道它具体是什么。
我们定义翻转的操作：把一个串以最后一个字符作对称轴进行翻转复制。形式化地描述就是，如果他翻转的串为 $R$ ，那么他会将前 $\left| R\right|-1$ 个字符倒序排列后，插入到串的最后。
举例而言，串 abcd 进行翻转操作后，将得到 abcdcba；串 qw 连续进行 $2$ 次翻转操作后，将得到 qwqwq；串 z 无论进行多少次翻转操作，都不会被改变。
贪玩的绿绿进行了若干次（可能为 $0$ 次）翻转操作。
淘气的绿绿又展示出了一个非空串 $S$ ，并表示 $S$ 是最终的串 $R$ 的前缀。现在，他想考考 Yazid，初始的串 $R$ 的长度可能是多少。
Yazid 找到了正在参加清华校赛的你，请你来帮他解决这个问题。但聪明的 Yazid 发现，所有超过 $\left| S\right|$ 的整数都一定是 $R$ 的可能长度，因此你只需要告诉他不超过的 $\left| S\right|$ 的 $R$ 的可能长度即可。
保证 $\left| S\right|\leq 10^6$ ， $\sum\left| S\right|\leq 5\times 10^6$ 。

什么样的字符串可以满足？以 $n$ 结尾的回文串一定可以。然后呢？我们来看 qwqwq 这个样例。

显然 qwq 是可以的，那么 qw 也是可以的。也就是说，如果 $1\sim 2i-1$ 是一个以 $i$ 为回文中心的回文串，那么这部分就可以由 $1\sim i$ 复制出来，只需要 $1\sim 2i-1$ 条件即可。这样就成了一个递归问题，递推求解即可。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

int m, n, p[10000010];
char t[5000005];
char s[10000010];
bool vis[10000010];

int main(void) {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%s", t + 1); m = strlen(t + 1);
        s[0] = '$'; s[n = 1] = '@';
        for (int i = 1; i <= m; ++i) s[++n] = t[i], s[++n] = '@';
        s[n + 1] = '!';
        fill(vis + 1, vis + n + 1, 0);
        for (int i = 1, d = 0, r = 0; i <= n; ++i) {
            if (i > r) p[i] = 1; else p[i] = min(r - i + 1, p[d * 2 - i]);
            while (s[i - p[i]] == s[i + p[i]]) ++p[i];
            if (i + p[i] - 1 > r) d = i, r = i + p[i] - 1;
        }
        for (int i = n; i >= 1; --i) {
            if (i + p[i] - 1 == n) vis[i] = 1;
            else if (i == p[i] && vis[i + p[i] - 2]) vis[i] = 1;
        }
        for (int i = 2; i <= n; i += 2)
            if (vis[i]) printf("%d ", i / 2);
        putchar('\n');
    }
    return 0;
}

KMP 模式匹配

很多时候我们使用 KMP 并不是为了求解字符串匹配，而是为了使用 $nxt$ 数组：以 $i$ 结尾的非前缀子串与 A 的前缀能够匹配的最大长度。

[CF126B] Password

Portal.

正反做两次 KMP，然后尝试将它们合并即可。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, nxt1[1000005], nxt2[1000005];
char s[1000005];

int main(void) {
    scanf("%s", s + 1); n = strlen(s + 1);
    for (int i = 2, p = 0; i <= n; ++i) {
        while (p && s[i] != s[p + 1]) p = nxt1[p];
        if (s[i] == s[p + 1]) ++p;
        nxt1[i] = p;
    }
    reverse(s + 1, s + n + 1);
    for (int i = 2, p = 0; i <= n; ++i) {
        while (p && s[i] != s[p + 1]) p = nxt2[p];
        if (s[i] == s[p + 1]) ++p;
        nxt2[i] = p;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (nxt1[i] == nxt2[n - i + nxt1[i]]) ans = max(ans, nxt1[i]);
    if (ans == 0) puts("Just a legend");
    else {
        for (int i = ans; i >= 1; --i)
            putchar(s[i]);
        putchar('\n');
    }
    return 0;
}

[CF808G] Anthem of Berland

Portal.

给定字符串 $s$ 和 $t$ ，但是 $s$ 中的一些字符丢失了。问 $t$ 在 $s$ 中最多出现多少次。两个字符串长度的乘积在 $10^7$ 级别。

考虑 DP。设 $f(i)$ 代表考虑到第 $i$ 位的最多出现次数，初始 $f(i)=f(i-1)$ 。除了能直接转移 $f(i)=f(i-m)+1$ ，中间可能还有 $t$ 。考虑对 $t$ 进行模式匹配，在中间寻找能够进行的转移即可。注意从这个转移过来的不能进行转移 $f(i)=f(i-m)+1$ 。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, m, nxt[100005], f[100005], g[100005];
char s[100005], t[100005];

bool check(int p) {
    if (p - m + 1 < 1) return false;
    for (int i = 1; i <= m; ++i)
        if (s[p - m + i] != '?' && s[p - m + i] != t[i]) return false;
    return true;
}

int main(void) {
    scanf("%s%s", s + 1, t + 1); n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 2, p = 0; i <= m; ++i) {
        while (p && t[i] != t[p + 1]) p = nxt[p];
        if (t[i] == t[p + 1]) ++p;
        nxt[i] = p;
    }
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1];
        if (check(i)) {
            g[i] = f[i - m] + 1;
            for (int j = nxt[m]; j; j = nxt[j])
                g[i] = max(g[i], g[i - m + j] + 1);
            f[i] = max(f[i], g[i]);
        }
    }
    printf("%d\n", f[n]);
    return 0;
}

[NOI2014] 动物园

Portal.

在 $nxt$ 数组上倍增即可。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MOD = 1000000007;

int nxt[22][1000005];
char s[1000005];

int main(void) {
    int T; scanf("%d", &T);
    int ans, n;
    while (T--) {
        scanf("%s", s + 1); n = strlen(s + 1), ans = 1;
        for (int i = 2, p = 0; i <= n; ++i) {
            while (p && s[i] != s[p + 1]) p = nxt[0][p];
            if (s[i] == s[p + 1]) ++p;
            nxt[0][i] = p;
        }
        for (int j = 1; j <= 19; ++j)
            for (int i = 1; i <= n; ++i)
                nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
        for (int i = 1; i <= n; ++i) {
            int p = i, cnt = 0;
            for (int j = 19; j >= 0; --j)
                if (nxt[j][p] * 2 > i) p = nxt[j][p];
            for (int j = 19; j >= 0; --j)
                if (nxt[j][p]) p = nxt[j][p], cnt += (1 << j);
            ans = 1ll * (cnt + 1) * ans % MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

[NOIP2020] 字符串匹配

Portal.

我们枚举 $(AB)$ 的长度和 $i$ ，求出 $nxt$ 数组用于判断这个 $i$ 是否合法。时间复杂度为 $O(n\log n)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1048580;

int n, nxt[N];
int pre[N], suf[N], cnt[26], tmp[27]; // tmp[i] 记录 A 中出现 0~i 个奇数字符的方案数
// pre[i] 记录 s[1...i] 中出现奇数字符的个数
char s[N];

void solve(void) {
    scanf("%s", s + 1); n = strlen(s + 1); suf[n + 1] = 0; 
    for (int i = 2, p = 0; i <= n; ++i) {
        while (p && s[i] != s[p + 1]) p = nxt[p];
        if (s[i] == s[p + 1]) ++p; nxt[i] = p; 
    } memset(cnt, 0, sizeof cnt);
    for (int i = n; i >= 1; --i) {
        ++cnt[s[i] - 'a'];
        if (cnt[s[i] - 'a'] & 1) suf[i] = suf[i + 1] + 1; 
        else suf[i] = suf[i + 1] - 1; 
    } memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i) {
        ++cnt[s[i] - 'a'];
        if (cnt[s[i] - 'a'] & 1) pre[i] = pre[i - 1] + 1; 
        else pre[i] = pre[i - 1] - 1; 
    } long long ans = 0; memset(tmp, 0, sizeof tmp);
    for (int i = 1; i < n; ++i) { // |AB| 的长度
        if (i >= 2) {
            ans += tmp[suf[i + 1]];
            for (int j = i + i; j < n && i % (j - nxt[j]) == 0; j += i)
                ans += tmp[suf[j + 1]]; 
        }
        for (int j = pre[i]; j <= 26; ++j) ++tmp[j];
    }
    printf("%lld\n", ans);
}

int main(void) {
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

实际上这是 MP 算法（KMP 在两个字符相等时会直接跳过），不过 MP 已经达到了理论时间复杂度下限。 ↩︎