字符串

字符串，就是由字符连接而成的序列。

常见的字符串问题包括字符串匹配问题、子串相关问题、前缀/后缀相关问题、回文串相关问题、子序列相关问题等。

字符串哈希

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

双值哈希 / 前缀哈希序列

令 $f_i(s) = f(s[1..i])$ 为字符串 s 的前缀哈希序列，预处理字符串 s 的前缀哈希序列。

1
2
3
4
5
6
constexpr u64 M = 1e9 + 7, M2 = (u64) 1e16 + 61, B = 133;
vector<u64> hs1(n + 2), hs2(n + 2);
for (int i = 1; i <= n; i++) {
    hs1[i] = (hs1[i - 1] * B + s[i - 1]) % M;
    hs2[i] = (hs2[i - 1] * B + s[i - 1]) % M2;
}

获取子串哈希值

注意到 $f(s[l+1..r])=f_r(s)-f_{l}(s) \times b^{r-l}$ 。

其中 $b^{r-l}$ 可以 $O(n)$ 的预处理出来然后 $O(1)$ 的回答每次询问。

对于回文子串问题，可以预处理字符串 s 与其反转字符串的前缀哈希序列，并 $O(1)$ 的判断回文子串。

注意下列实现中查询区间左开右闭，即查询 $f(s[l+1..r])$。

1
2
3
4
5
6
7
8
vector<u64> b1(n + 2, 1), b2(n + 2, 1)
for (int i = 1; i <= n; i++) {
    b1[i] = b1[i - 1] * B % M;
    b2[i] = b2[i - 1] * B % M2;
}

u64 h1 = (hs1[r] - hs1[l] * b1[r - l] % M + M) % M;
u64 h2 = (hs2[r] - (u128) hs2[l] * b2[r - l] % M2 + M2) % M2;

KMP 算法

查询模式串在文本中的出现次数，使用 $init$ 函数获得 $pre$ 数组，按需更改返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> pre;

void init(const string &pat) {
    int n = (int) pat.size();
    pre.resize(n);
    for (int i = 1, j = 0; i < n; i++) {
        while (j > 0 && pat[i] != pat[j]) j = pre[j - 1];
        if (pat[i] == pat[j]) j++;
        pre[i] = j;
    }
}

int kmp(const string &txt, const string &pat, int pos = 0) {
    if (pat.empty()) return 0;
    int n = (int) pat.size(), cnt = 0;
    for (int i = pos, j = 0; i < txt.size(); i++) {
        while (j > 0 && txt[i] != pat[j]) j = pre[j - 1];
        if (txt[i] == pat[j]) j++;
        // if (j == n) return i - n + 1; // 返回第一次出现的模式串下标
        if (j == n) cnt++, j = pre[j - 1];
    }
    return cnt; // 返回模式串个数
}

Manacher 算法

Manacher 算法可以在 $\Theta(n)$ 的时间内处理出回文半径数组，原字符串下标 $i$ 的字符对应新字符串下标 $i*2+1$ ，回文串判断函数左闭右闭实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> p;
auto manacher = [&](const string &str) {
    string t = "#";
    for (char ch: str) t += ch, t += "#";
    p.resize(t.size());
    int len = (int) t.size(), c = 0, r = 0;
    for (int i = 1; i < len - 1; ++i) {
        if (i < r) p[i] = min(r - i, p[2 * c - i]);
        while (i + p[i] + 1 < len && i - p[i] - 1 >= 0 && t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;
        if (i + p[i] > r) c = i, r = i + p[i];
    }
};
manacher(s);

auto palindromic = [&](int l, int r) {
    return p[l + r + 1] >= r - l + 1;
}

字典树

一个像字典一样的树，用边来代表字符，从根结点到树上某一结点的路径就代表了一个字符串。

字典树

最基本的字典树，维护了边数、前缀路径对应字符串的数量和前缀路径对应字符串作为前缀的字符串数量，其中 $get$ 函数定义了字符到下标的转换。

支持新增字符串、删除字符串与查询字符串数量，单次操作时间复杂度均为 $O(L)$ ，插入操作空间复杂度 $O(L×K)$ ，其中 $L$ 为字符串长度， $K$ 为字符集大小。

array 的动态开点需求 c++17，若版本不足需要在构造函数提前开好足量 ch 数组大小，并修改 create 函数。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct Trie {  
    int sz;  
    vector<array<int, 26> > ch;  
    vector<int> pre, cnt;  
  
    explicit Trie() : ch(1), pre(1), cnt(1) {  
        sz = 0;  
    }  
  
    static int id(char c) {  
        return c - 'a';  
    }  
  
    int create() {  
        int x = ch.size();  
        ch.emplace_back();  
        pre.push_back(0);  
        cnt.push_back(0);  
        return x;  
    }  
  
    void insert(const string &s) {  
        int p = 0;  
        pre[p]++;  
        for (char c: s) {  
            int i = id(c);  
            if (!ch[p][i]) ch[p][i] = create();  
            p = ch[p][i];  
            sz += pre[p]++ == 0;  
        }  
        cnt[p]++;  
    }  
  
    void remove(const string &s) {  
        int p = 0;  
        --pre[p];  
        for (char c: s) {  
            int i = id(c);  
            p = ch[p][i];  
            sz -= --pre[p] == 0;  
        }  
        --cnt[p];  
    }  
  
    int find(const string &s) {  
        int p = 0;  
        for (char c: s) {  
            int i = id(c);  
            if (!ch[p][i]) return 0;  
            p = ch[p][i];  
        }  
        return cnt[p];  
    }  
};

AC 自动机

数组实现的字典树，支持构建 AC 自动机，使用拓扑排序优化匹配。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
template<char S, int N>
struct Trie {
    vector<int> cnt, ans, indeg;
    vector<array<int, N> > ch;
    vector<int> fa;

    Trie() : ch(1), cnt(1), ans(0), indeg(0), fa(0) {}

    void insert(const string &s) {
        int p = 0;
        for (char c: s) {
            int i = c - S;
            if (!ch[p][i]) {
                ch[p][i] = (int) ch.size();
                ch.emplace_back();
                cnt.push_back(0);
            }
            p = ch[p][i];
        }
        cnt[p]++;
    }

    void build() {
        queue<int> q;
        for (auto p: ch[0]) {
            if (p) q.push(p);
        }
        fa.resize(cnt.size());
        indeg.resize(cnt.size());
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < N; i++) {
                int &p = ch[u][i];
                if (p) {
                    fa[p] = ch[fa[u]][i];
                    indeg[ch[fa[u]][i]]++;
                    q.push(p);
                } else {
                    p = ch[fa[u]][i];
                }
            }
        }
    }

    void topu() {
        queue<int> q;
        for (int i = 0; i < cnt.size(); i++)
            if (!indeg[i]) q.push(i);
        while (!q.empty()) {
            int fr = q.front();
            q.pop();
            int u = fa[fr];
            ans[u] += ans[fr];
            if (!(--indeg[u])) q.push(u);
        }
    }

    void match(const string &s, bool multiple = false) {
        ans.resize(cnt.size());
        int i = 0;
        for (auto c: s) {
            i = ch[i][c - S];
            ans[i] += multiple ? cnt[i] : 1;
            /*for (int j = i; j; j = fa[j]) {
                if (cnt[j]) ans[j] += multiple ? cnt[j] : 1;
            }*/
        }
    }

    int query(const string &s) {
        int p = 0;
        for (char c: s) {
            if (!ch[p][c - S]) return 0;
            p = ch[p][c - S];
        }
        return ans[p];
    }

    int find(const string &s) {
        int p = 0;
        for (char c: s) {
            if (!ch[p][c - S]) return 0;
            p = ch[p][c - S];
        }
        return cnt[p];
    }
};

后缀数组

后缀数组是一种将字符串所有后缀按字典序排序的数据结构。

  1. 最长重复子串：在后缀数组上相邻后缀的最长公共前缀（LCP）的最大值即为答案。
  2. 不同子串计数：总子串数减去相邻后缀的 LCP 之和，即 $\frac{n(n+1)}{2} - \sum_{i=1}^{n-1} \text{LCP}[i]$ 。
  3. 最长回文子串：将原串与反串拼接，中间加分隔符，枚举每个中心点并在 SA 上查询前后缀的 LCP 。
  4. 多串最长公共子串：拼接所有串并加分隔符，在 SA 上滑动窗口求包含所有串的区间的最小 LCP 最大值。
  5. 字典序第 k 小子串：利用 SA 和 LCP 数组二分答案，计算不同子串数量的前缀和。
  6. 字符串循环移位最小表示：将字符串复制一份接在后面，构建 SA 后找首个长度 ≥n 的后缀起始位置。
  7. 最长公共扩展查询（LCE）：直接使用 SA 的 LCP 数组结合 RMQ 快速查询任意两后缀的 LCP 。
  8. 字符串匹配：在 SA 上二分查找模式串，检查是否存在匹配的前缀。

以下代码使用倍增算法和基数排序构建后缀数组，使用 Kasai 算法计算高度数组，并预处理 ST 表优化区间最小值查询，总构建复杂度 $O(n\log{n})$ ，查询复杂度 $O(1)$ 。

注意 $st[0][i]=lcp(sa[i],sa[i+1])$ ，即 st 表下标范围为 $[0,n-1)$，且 rmq 函数使用左闭右开实现。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct SuffixArray {  
    int n;  
    vector<int> sa, rk;  
    vector<vector<int> > st;  
  
    explicit SuffixArray(const string &s) : n(s.size()), sa(n), rk(n), st(__lg(n - 1) + 1, vector<int>(n - 1)) {  
        iota(sa.begin(), sa.end(), 0);  
        ranges::sort(sa, [&](int a, int b) { return s[a] < s[b]; });  
        for (int i = 1; i < n; i++) rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);;  
        vector<int> tmp(n), cnt(n);  
        for (int k = 1; rk[sa[n - 1]] < n - 1; k <<= 1) {  
            tmp.clear();  
            for (int i = 0; i < k; i++) tmp.push_back(n - k + i);  
            for (auto i: sa) if (i >= k) tmp.push_back(i - k);  
            ranges::fill(cnt, 0);  
            for (int i = 0; i < n; i++) cnt[rk[i]]++;  
            for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];  
            for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i];  
            swap(rk, tmp);  
            rk[sa[0]] = 0;  
            for (int i = 1; i < n; i++) {  
                int inc = tmp[sa[i - 1]] != tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] != tmp[sa[i] + k];  
                rk[sa[i]] = rk[sa[i - 1]] + inc;  
            }  
        }  
        for (int i = 0, j = 0; i < n; i++) {  
            if (rk[i] == 0) continue;  
            for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; j++) {  
            }  
            st[0][rk[i] - 1] = j;  
        }  
        for (int j = 1; j <= __lg(n - 1); j++) {  
            for (int i = 0; i + (1 << j) <= n - 1; i++) {  
                st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);  
            }  
        }  
    }  
  
    int rmq(int l, int r) {  
        int k = __lg(r - l);  
        return min(st[k][l], st[k][r - (1 << k)]);  
    }  
  
    int lcp(int i, int j) {  
        if (i == j || i == n || j == n) return min(n - i, n - j);  
        int a = rk[i], b = rk[j];  
        if (a > b) swap(a, b);  
        return min({n - i, n - j, rmq(a, b)});  
    }  
};