CSES String Algorithm

更新ing

2026-01-18：还差两道目测和后缀数组有关系，明天再学。

NOTE
前三道是之前写过的，有些不严谨的地方懒得改了，字符串哈希参考后面的冲突率更低。

Word Combinations#

用 kmp 把词在串里出现的位置算出来标记上，然后做线性 DP。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
const int MOD = 1000000007;
7
int ne[1000010], f[5010];
8
vector<int> l[5010];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    string s, t;
14
    int n, k;
15
    cin >> s;
16
    n = s.length();
17
    cin >> k;
18
    while (k--) {
19
        cin >> t;
20
        for (int i = 2, j = 0; i <= t.length(); ++i) {
21
            while (j && t[i - 1] != t[j]) j = ne[j];
22
            if (t[i - 1] == t[j]) j++;
23
            ne[i] = j;
24
        }
25
        for (int i = 1, j = 0; i <= n; ++i) {
26
            while (j && s[i - 1] != t[j]) j = ne[j];
27
            if (s[i - 1] == t[j]) j++;
28
            if (j == t.length()) {
29
                l[i].push_back(t.length());
30
                j = ne[j];
31
            }
32
        }
33
    }
34
    f[0] = 1;
35
    for (int i = 1; i <= n; ++i) {
36
        for (int j : l[i]) {
37
            f[i] = (f[i] + f[i - j]) % MOD;
38
        }
39
    }
40
    cout << f[n] << endl;
41
    return 0;
42
}

String Matching#

KMP 纯板子。

1
#include <iostream>
2

3
using namespace std;
4

5
int ne[1000010];
6

7
int main() {
8
    ios::sync_with_stdio(0);
9
    cin.tie(0), cout.tie(0);
10
    string s, t;
11
    int res = 0;
12
    cin >> s >> t;
13
    for (int i = 2, j = 0; i <= t.length(); ++i) {
14
        while (j && t[i - 1] != t[j]) j = ne[j];
15
        if (t[i - 1] == t[j]) j++;
16
        ne[i] = j;
17
    }
18
    for (int i = 0, j = 0; i < s.length(); ++i) {
19
        while (j && s[i] != t[j]) j = ne[j];
20
        if (s[i] == t[j]) j++;
21
        if (j == t.length()) {
22
            res++;
23
            j = ne[j];
24
        }
25
    }
26
    cout << res << endl;
27
    return 0;
28
}

Finding Borders#

暴力枚举，用字符串哈希比较。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int MOD = 1000000007;
7
long long H[1000010], p[1000010];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    string s;
13
    cin >> s;
14
    p[0] = 1;
15
    int n = s.length();
16
    for (int i = 1; i <= n; ++i) {
17
        H[i] = (H[i - 1] * 26 + (s[i - 1] - 'a')) % MOD;
18
        p[i] = p[i - 1] * 26 % MOD;
19
    }
20
    for (int i = 1; i < n; ++i) {
21
        if (H[i] == ((H[n] - H[n - i] * p[i] % MOD) % MOD + MOD) % MOD) {
22
            cout << i << ' ';
23
        }
24
    }
25
    cout << endl;
26
    return 0;
27
}

Finding Periods#

NOTE
这道题看了题解。

哈希暴力对比就行了，我在想什么，调和级数级别的时间复杂度完全可以接受。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 1000010;
7
uint64_t h1[N], h2[N], p1[N], p2[N];
8

9
uint64_t get1(int l, int r) {
10
    return h1[l - 1] * p1[r - l + 1] - h1[r];
11
}
12

13
uint64_t get2(int l, int r) {
14
    return h2[l - 1] * p2[r - l + 1] - h2[r];
15
}
16

17
int main() {
18
    ios::sync_with_stdio(0);
19
    cin.tie(0), cout.tie(0);
20
    string s;
21
    cin >> s;
22
    int n = s.length();
23
    p1[0] = p2[0] = 1;
24
    for (int i = 1; i <= n; ++i) {
25
        p1[i] = p1[i - 1] * 131;
26
        p2[i] = p2[i - 1] * 1331;
27
        h1[i] = h1[i - 1] * 131 + s[i - 1];
28
        h2[i] = h2[i - 1] * 1331 + s[i - 1];
29
    }
30
    for (int i = 1; i <= n; ++i) {
31
        bool f = true;
32
        for (int j = i + 1; j <= n; j += i) {
33
            int len = min(n - j + 1, i);
34
            if (get1(1, len) != get1(j, j + len - 1) || get2(1, len) != get2(j, j + len - 1)) {
35
                f = false;
36
                break;
37
            }
38
        }
39
        if (f) cout << i << ' ';
40
    }
41
    cout << endl;
42
    return 0;
43
}

Minimal Rotation#

比较两个串的大小可以用哈希 + 二分（二分第一个哈希值不一样的前缀，比较最后一位大小）优化成 log，然后暴力处理时间复杂度就成了 $O(n \log n)$ 。

怎么会有人蠢到暴力枚举能少枚举呢😭，wa 了好几发。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 2000010;
7
uint64_t h1[N], h2[N], p1[N], p2[N];
8

9
uint64_t get1(int l, int r) {
10
    return h1[l - 1] * p1[r - l + 1] - h1[r];
11
}
12

13
uint64_t get2(int l, int r) {
14
    return h2[l - 1] * p2[r - l + 1] - h2[r];
15
}
16

17
int main() {
18
    ios::sync_with_stdio(0);
19
    cin.tie(0), cout.tie(0);
20
    string s;
21
    cin >> s;
22
    int n = s.length(), p = 1;
23
    s = " " + s + s;
24
    p1[0] = p2[0] = 1;
25
    for (int i = 1; i <= n * 2; ++i) {
26
        p1[i] = p1[i - 1] * 131;
27
        p2[i] = p2[i - 1] * 1331;
28
        h1[i] = h1[i - 1] * 131 + s[i];
29
        h2[i] = h2[i - 1] * 1331 + s[i];
30
    }
31
    for (int i = 2; i <= n; ++i) {
32
        int l = 1, r = n + 1;
33
        while (l < r) {
34
            int mid = l + r >> 1;
35
            if (get1(p, p + mid - 1) != get1(i, i + mid - 1) || get2(p, p + mid - 1) != get2(i, i + mid - 1)) r = mid;
36
            else l = mid + 1;
37
        }
38
        if (l == n + 1) continue;
39
        else if (s[i + l - 1] < s[p + l - 1]) p = i;
40
    }
41
    cout << s.substr(p, n) << endl;
42
    return 0;
43
}

Longest Palindrome#

仍然可以哈希 + 二分，正着和反着分别维护一遍哈希表，然后暴力枚举中间点下标，二分回文子串的长度。我感觉可能是因为自然溢出需要都是同一个串的前缀所以会出错，这里哈希需要取模。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5
typedef long long LL;
6
const int N = 1000010;
7
const int MOD = 998244353;
8
int64_t h1[N], h2[N], h1r[N], h2r[N], p1[N], p2[N];
9

10
int64_t get1(int l, int r) {
11
    return (h1[r] - h1[l - 1] * p1[r - l + 1] % MOD + MOD) % MOD;
12
}
13

14
int64_t get2(int l, int r) {
15
    return (h2[r] - h2[l - 1] * p2[r - l + 1] % MOD + MOD) % MOD;
16
}
17

18
int64_t get1r(int l, int r) {
19
    return (h1r[l] - h1r[r + 1] * p1[r - l + 1] % MOD + MOD) % MOD;
20
}
21

22
int64_t get2r(int l, int r) {
23
    return (h2r[l] - h2r[r + 1] * p2[r - l + 1] % MOD + MOD) % MOD;
24
}
25

26
int main() {
27
    ios::sync_with_stdio(0);
28
    cin.tie(0), cout.tie(0);
29
    string s;
30
    cin >> s;
31
    int n = s.length(), p = 1, len = 1;
32
    s = " " + s;
33
    p1[0] = p2[0] = 1;
34
    for (int i = 1; i <= n; ++i) {
35
        p1[i] = p1[i - 1] * 131 % MOD;
36
        p2[i] = p2[i - 1] * 1331 % MOD;
37
        h1[i] = (h1[i - 1] * 131 + s[i]) % MOD;
38
        h2[i] = (h2[i - 1] * 1331 + s[i]) % MOD;
39
    }
40
    for (int i = n; i; --i) {
41
        h1r[i] = (h1r[i + 1] * 131 + s[i]) % MOD;
42
        h2r[i] = (h2r[i + 1] * 1331 + s[i]) % MOD;
43
    }
44
    for (int i = 2; i < n; ++i) {
45
        int l = 0, r = min(n - i, i - 1);
46
        while (l < r) {
47
            int mid = l + r + 1 >> 1;
48
            if (get1(i + 1, i + mid) == get1r(i - mid, i - 1) && get2(i + 1, i + mid) == get2r(i - mid, i - 1)) l = mid;
49
            else r = mid - 1;
50
        }
51
        if (l * 2 + 1 > len) p = i - l, len = l * 2 + 1;
52
    }
53
    for (int i = 1; i < n; ++i) {
54
        int l = 0, r = min(n - i, i);
55
        while (l < r) {
56
            int mid = l + r + 1 >> 1;
57
            if (get1(i + 1, i + mid) == get1r(i - mid + 1, i) && get2(i + 1, i + mid) == get2r(i - mid + 1, i)) l = mid;
58
            else r = mid - 1;
59
        }
60
        if (l * 2 > len) p = i - l + 1, len = l * 2;
61
    }
62
    cout << s.substr(p, len) << endl;
63
    return 0;
64
}

Required Substring#

可以 DP，维护 $f_{i, j}$ 表示前 $i$ 个并且末尾已经匹配了 $j$ 个的方案数，已经成功匹配一次的全算到 $f_{i, m}$ 里面。更新的时候考虑试填字母模拟 KMP 的过程，找到填完之后仍能匹配几个。

1
#include <iostream>
2
#include <set>
3
using namespace std;
4
typedef long long LL;
5
const int MOD = 1000000007;
6
const int N = 1010, M = 110;
7
LL f[N][M];
8
int ne[M];
9
set<int> s;
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n, m;
15
    string s;
16
    cin >> n >> s;
17
    m = s.length();
18
    for (int i = 2, j = 0; i <= m; ++i) {
19
        while (j && s[i - 1] != s[j]) j = ne[j];
20
        if (s[i - 1] == s[j]) j++;
21
        ne[i] = j;
22
    }
23
    f[0][0] = 1;
24
    for (int i = 1; i <= n; ++i) {
25
        f[i][m] = f[i - 1][m] * 26 % MOD;
26
        for (int j = 0; j < m; ++j) {
27
            set<char> ss;
28
            for (char c = 'A'; c <= 'Z'; ++c) ss.insert(c);
29
            int k = j;
30
            while (k) {
31
                f[i][k + 1] = (f[i][k + 1] + f[i - 1][j] * ss.count(s[k])) % MOD;
32
                ss.erase(s[k]);
33
                k = ne[k];
34
            }
35
            f[i][1] = (f[i][1] + f[i - 1][j] * ss.count(s[0])) % MOD;
36
            ss.erase(s[0]);
37
            f[i][0] = (f[i][0] + f[i - 1][j] * ss.size()) % MOD;
38
        }
39
    }
40
    cout << f[n][m] << endl;
41
    return 0;
42
}

Palindrome Queries#

可以用哈希，正向和反向哈希值一样就说明是回文的，动态的哈希可以用树状数组或者线段树做。我用了树状数组。

1
#include <iostream>
2
#include <set>
3
using namespace std;
4
typedef long long LL;
5
const int N = 200010, MOD = 998244353;
6

7
LL p1[N], p2[N];
8
int n;
9
struct FenwickTree {
10
    LL tr[N];
11

12
    void add(int u, LL val) {
13
        for (; u <= n; u += u & -u) {
14
            tr[u] = (tr[u] + val) % MOD;
15
        }
16
    }
17

18
    LL query(int u) {
19
        LL res = 0;
20
        for (; u; u -= u & -u) {
21
            res = (res + tr[u]) % MOD;
22
        }
23
        return res;
24
    }
25
} tr1, tr2, tr1r, tr2r;
26

27
LL power(LL n, LL p) {
28
    LL res = 1, base = n;
29
    while (p) {
30
        if (p & 1) res = res * base % MOD;
31
        base = base * base % MOD;
32
        p >>= 1;
33
    }
34
    return res;
35
}
36

37
int main() {
38
    ios::sync_with_stdio(0);
39
    cin.tie(0), cout.tie(0);
40
    int m;
41
    string s;
42
    cin >> n >> m >> s;
43
    s = " " + s;
44
    p1[0] = p2[0] = 1;
45
    for (int i = 1; i <= n; ++i) {
46
        p1[i] = p1[i - 1] * 131 % MOD;
47
        p2[i] = p2[i - 1] * 1331 % MOD;
48
    }
49
    for (int i = 1; i <= n; ++i) {
50
        tr1.add(i, p1[n - i] * s[i]);
51
        tr2.add(i, p2[n - i] * s[i]);
52
        tr1r.add(i, p1[i - 1] * s[i]);
53
        tr2r.add(i, p2[i - 1] * s[i]);
54
    }
55
    while (m--) {
56
        int op;
57
        cin >> op;
58
        if (op == 1) {
59
            int k;
60
            char x;
61
            cin >> k >> x;
62
            tr1.add(k, -p1[n - k] * s[k]);
63
            tr2.add(k, -p2[n - k] * s[k]);
64
            tr1r.add(k, -p1[k - 1] * s[k]);
65
            tr2r.add(k, -p2[k - 1] * s[k]);
66
            s[k] = x;
67
            tr1.add(k, p1[n - k] * s[k]);
68
            tr2.add(k, p2[n - k] * s[k]);
69
            tr1r.add(k, p1[k - 1] * s[k]);
70
            tr2r.add(k, p2[k - 1] * s[k]);
71
        }
72
        else {
73
            int l, r;
74
            cin >> l >> r;
75
            LL h1 = (tr1.query(r) - tr1.query(l - 1) + MOD) % MOD * power(p1[n - r], MOD - 2) % MOD;
76
            LL h2 = (tr2.query(r) - tr2.query(l - 1) + MOD) % MOD * power(p2[n - r], MOD - 2) % MOD;
77
            LL h1r = (tr1r.query(r) - tr1r.query(l - 1) + MOD) % MOD * power(p1[l - 1], MOD - 2) % MOD;
78
            LL h2r = (tr2r.query(r) - tr2r.query(l - 1) + MOD) % MOD * power(p2[l - 1], MOD - 2) % MOD;
79
            cout << (h1 == h1r && h2 == h2r ? "YES" : "NO") << endl;
80
        }
81
    }
82
    return 0;
83
}

Finding Patterns#

AC 自动机（实际上最好用优化版的 Trie 图）的板子，需要注意打访问标记否则时间复杂度不对。

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
using namespace std;
5
typedef long long LL;
6
const int N = 500010;
7

8
int trie[N][26], ne[N], tot = 0;
9
bool v[N];
10
vector<int> flag[N];
11
bool res[N];
12

13
void insert(string t, int flg) {
14
    int p = 0;
15
    for (char c : t) {
16
        if (trie[p][c - 'a']) p = trie[p][c - 'a'];
17
        else trie[p][c - 'a'] = ++tot, p = tot;
18
    }
19
    flag[p].emplace_back(flg);
20
}
21

22
void build() {
23
    queue<int> q;
24
    for (int i = 0; i < 26; ++i) {
25
        if (trie[0][i]) q.emplace(trie[0][i]);
26
    }
27
    while (!q.empty()) {
28
        int x = q.front();
29
        q.pop();
30
        for (int i = 0; i < 26; ++i) {
31
            int &y = trie[x][i];
32
            if (!y) y = trie[ne[x]][i];
33
            else {
34
                ne[y] = trie[ne[x]][i];
35
                q.emplace(y);
36
            }
37
        }
38
    }
39
}
40

41
int main() {
42
    ios::sync_with_stdio(0);
43
    cin.tie(0), cout.tie(0);
44
    string s, t;
45
    int n, m;
46
    cin >> s >> m;
47
    n = s.length();
48
    for (int i = 1; i <= m; ++i) {
49
        cin >> t;
50
        insert(t, i);
51
    }
52
    build();
53
    for (int i = 1, j = 0; i <= n; ++i) {
54
        j = trie[j][s[i - 1] - 'a'];
55
        int p = j;
56
        while (p && !v[p]) {
57
            for (int idx : flag[p]) res[idx] = true;
58
            v[p] = true;
59
            p = ne[p];
60
        }
61
    }
62
    for (int i = 1; i <= m; ++i) {
63
        cout << (res[i] ? "YES" : "NO") << endl;
64
    }
65
    return 0;
66
}

Counting Patterns#

AC 自动机板子，如果不优化可能会造成 TLE，先不下传答案，都记到第一个匹配的位置，最后拓扑排序一并更新答案，保证时间复杂度是线性的。

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
using namespace std;
5
typedef long long LL;
6
const int N = 500010;
7

8
int trie[N][26], ne[N], f[N], deg[N], tot = 0;
9
bool v[N];
10
string t[N];
11
vector<int> flag[N];
12

13
void insert(string t, int flg) {
14
    int p = 0;
15
    for (char c : t) {
16
        if (trie[p][c - 'a']) p = trie[p][c - 'a'];
17
        else trie[p][c - 'a'] = ++tot, p = tot;
18
    }
19
    flag[p].emplace_back(flg);
20
}
21

22
void build() {
23
    queue<int> q;
24
    for (int i = 0; i < 26; ++i) {
25
        if (trie[0][i]) q.emplace(trie[0][i]);
26
    }
27
    while (!q.empty()) {
28
        int x = q.front();
29
        q.pop();
30
        for (int i = 0; i < 26; ++i) {
31
            int &y = trie[x][i];
32
            if (!y) y = trie[ne[x]][i];
33
            else {
34
                ne[y] = trie[ne[x]][i];
35
                deg[ne[y]]++;
36
                q.emplace(y);
37
            }
38
        }
39
    }
40
}
41

42
int query(string t) {
43
    int p = 0;
44
    for (char c : t) {
45
        p = trie[p][c - 'a'];
46
    }
47
    return f[p];
48
}
49

50
int main() {
51
    ios::sync_with_stdio(0);
52
    cin.tie(0), cout.tie(0);
53
    string s;
54
    int n, m;
55
    cin >> s >> m;
56
    n = s.length();
57
    for (int i = 1; i <= m; ++i) {
58
        cin >> t[i];
59
        insert(t[i], i);
60
    }
61
    build();
62
    for (int i = 1, j = 0; i <= n; ++i) {
63
        j = trie[j][s[i - 1] - 'a'];
64
        f[j]++;
65
    }
66
    queue<int> q;
67
    for (int i = 0; i <= tot; ++i) {
68
        if (!deg[i]) q.emplace(i);
69
    }
70
    while (!q.empty()) {
71
        int x = q.front();
72
        q.pop();
73
        f[ne[x]] += f[x];
74
        if (--deg[ne[x]] == 0) q.emplace(ne[x]);
75
    }
76
    for (int i = 1; i <= m; ++i) {
77
        cout << query(t[i]) << endl;
78
    }
79
    return 0;
80
}

Pattern Positions#

还是 AC 自动机的板子，这次是找第一次出现的位置。

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <cstring>
5
using namespace std;
6
typedef long long LL;
7
const int N = 500010;
8

9
int trie[N][26], ne[N], tot = 0;
10
int res[N];
11
bool v[N];
12
string t[N];
13
vector<int> flag[N];
14

15
void insert(string t, int flg) {
16
    int p = 0;
17
    for (char c : t) {
18
        if (trie[p][c - 'a']) p = trie[p][c - 'a'];
19
        else trie[p][c - 'a'] = ++tot, p = tot;
20
    }
21
    flag[p].emplace_back(flg);
22
}
23

24
void build() {
25
    queue<int> q;
26
    for (int i = 0; i < 26; ++i) {
27
        if (trie[0][i]) q.emplace(trie[0][i]);
28
    }
29
    while (!q.empty()) {
30
        int x = q.front();
31
        q.pop();
32
        for (int i = 0; i < 26; ++i) {
33
            int &y = trie[x][i];
34
            if (!y) y = trie[ne[x]][i];
35
            else {
36
                ne[y] = trie[ne[x]][i];
37
                q.emplace(y);
38
            }
39
        }
40
    }
41
}
42

43
int main() {
44
    ios::sync_with_stdio(0);
45
    cin.tie(0), cout.tie(0);
46
    string s;
47
    int n, m;
48
    cin >> s >> m;
49
    n = s.length();
50
    for (int i = 1; i <= m; ++i) {
51
        cin >> t[i];
52
        insert(t[i], i);
53
    }
54
    build();
55
    for (int i = 1, j = 0; i <= n; ++i) {
56
        j = trie[j][s[i - 1] - 'a'];
57
        int p = j;
58
        while (p && !v[p]) {
59
            for (int idx : flag[p]) res[idx] = i;
60
            v[p] = true;
61
            p = ne[p];
62
        }
63
    }
64
    for (int i = 1; i <= m; ++i) {
65
        if (!res[i]) cout << -1 << endl;
66
        else cout << res[i] - t[i].length() + 1 << endl;
67
    }
68
    return 0;
69
}

Distinct Substrings#

这个是后缀自动机的板子题，结点 i 子串数量就是 $len(i) - len(fa(i))$ ，全部求和即可。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
const int N = 200010;
7

8
int last = 1, tot = 1;
9
struct Node {
10
    int len, fa;
11
    int ch[26];
12
} node[N];
13

14
void extend(int c) {
15
    int p = last, np = last = ++tot;
16
    node[np].len = node[p].len + 1;
17
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = tot;
18
    if (!p) node[np].fa = 1;
19
    else {
20
        int q = node[p].ch[c];
21
        if (node[q].len == node[p].len + 1) node[np].fa = q;
22
        else {
23
            int nq = ++tot;
24
            node[nq] = node[q], node[nq].len = node[p].len + 1;
25
            node[np].fa = node[q].fa = nq;
26
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
27
        }
28
    }
29
}
30

31
int main() {
32
    ios::sync_with_stdio(0);
33
    cin.tie(0), cout.tie(0);
34
    string s;
35
    int n;
36
    cin >> s;
37
    for (char c : s) extend(c - 'a');
38
    long long res = 0;
39
    for (int i = 1; i <= tot; ++i) {
40
        res += node[i].len - node[node[i].fa].len;
41
    }
42
    cout << res << endl;
43
    return 0;
44
}

Distinct Subsequences#

NOTE
这道题看了题解。

线性 DP，从左到右考虑每一位填不填，唯一可能算重的情况是 ... a ... a，第二个 a 和第一个 a 只选一个且中间一个也没选，减掉一份前面的即可。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 500010, MOD = 1000000007;
7
int ls[26];
8
LL f[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    string s;
14
    int n;
15
    cin >> s;
16
    n = s.length();
17
    s = " " + s;
18
    f[0] = 1;
19
    for (int i = 1; i <= n; ++i) {
20
        int c = s[i] - 'a';
21
        if (!ls[c]) f[i] = f[i - 1] * 2 % MOD;
22
        else f[i] = ((f[i - 1] * 2 - f[ls[c] - 1]) % MOD + MOD) % MOD;
23
        ls[c] = i;
24
    }
25
    cout << (f[n] + MOD - 1) % MOD << endl;
26
    return 0;
27
}

Repeating Substring#

构建后缀自动机的时候记录一下最长的路径是从哪里来的，或者在后缀自动机上 dfs，限制只能走长度 + 1 的边（这样能保证是字典序最小的一个，不会因为没有 spj 被卡掉）。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 200010;
6

7
int last = 1, tot = 1;
8
struct Node {
9
    int len, fa;
10
    int ch[26];
11
} node[N];
12
int f[N];
13
bool v[N];
14
int head[N], ne[N], ver[N], cnt;
15

16
void add(int x, int y) {
17
    ver[++cnt] = y;
18
    ne[cnt] = head[x];
19
    head[x] = cnt;
20
}
21

22
void extend(int c) {
23
    int p = last, np = last = ++tot;
24
    node[np].len = node[p].len + 1;
25
    f[np] = 1;
26
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
27
    if (!p) node[np].fa = 1;
28
    else {
29
        int q = node[p].ch[c];
30
        if (node[q].len == node[p].len + 1) node[np].fa = q;
31
        else {
32
            int nq = ++tot;
33
            node[nq] = node[q], node[nq].len = node[p].len + 1;
34
            node[np].fa = node[q].fa = nq;
35
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
36
        }
37
    }
38
}
39

40
void dfs(int x) {
41
    for (int i = head[x]; i; i = ne[i]) {
42
        dfs(ver[i]);
43
        f[x] += f[ver[i]];
44
    }
45
}
46

47
string res;
48
int mxlen;
49

50
bool dfs2(int x) {
51
    if (v[x]) return false;
52
    v[x] = true;
53
    if (f[x] != 1 && mxlen == node[x].len) {
54
        return true;
55
    }
56
    else {
57
        for (int i = 0; i < 26; ++i) {
58
            if (node[x].len + 1 == node[node[x].ch[i]].len) {
59
                res += 'a' + i;
60
                if (dfs2(node[x].ch[i])) return true;
61
                res.pop_back();
62
            }
63
        }
64
    }
65
    return false;
66
}
67

68
int main() {
69
    ios::sync_with_stdio(0);
70
    cin.tie(0), cout.tie(0);
71
    string s;
72
    int n;
73
    cin >> s;
74
    for (char c : s) extend(c - 'a');
75
    for (int i = 2; i <= tot; ++i) {
76
        add(node[i].fa, i);
77
    }
78
    dfs(1);
79
    for (int i = 1; i <= tot; ++i) {
80
        if (f[i] != 1) mxlen = max(mxlen, node[i].len);
81
    }
82
    if (mxlen == 0) {
83
        cout << -1 << endl;
84
        return 0;
85
    }
86
    dfs2(1);
87
    cout << res << endl;
88
    return 0;
89
}

String Functions#

第一行可以用字符串哈希 + 二分做，第二行其实就是 KMP 的 next 数组。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1000010;
6
uint64_t h1[N], h2[N], p1[N], p2[N];
7
int ne[N];
8

9
uint64_t get1(int l, int r) {
10
    return h1[l - 1] * p1[r - l + 1] - h1[r];
11
}
12

13
uint64_t get2(int l, int r) {
14
    return h2[l - 1] * p2[r - l + 1] - h2[r];
15
}
16

17
int main() {
18
    ios::sync_with_stdio(0);
19
    cin.tie(0), cout.tie(0);
20
    string s;
21
    cin >> s;
22
    int n = s.length();
23
    s = " " + s;
24
    p1[0] = p2[0] = 1;
25
    for (int i = 1; i <= n; ++i) {
26
        h1[i] = h1[i - 1] * 131 + s[i];
27
        h2[i] = h2[i - 1] * 1331 + s[i];
28
        p1[i] = p1[i - 1] * 131;
29
        p2[i] = p2[i - 1] * 1331;
30
    }
31
    for (int i = 1; i <= n; ++i) {
32
        if (i == 1) {
33
            cout << 0 << ' ';
34
            continue;
35
        }
36
        int l = 0, r = n - i + 1;
37
        while (l < r) {
38
            int mid = l + r + 1 >> 1;
39
            if (get1(1, 1 + mid - 1) == get1(i, i + mid - 1) && get2(1, 1 + mid - 1) == get2(i, i + mid - 1)) l = mid;
40
            else r = mid - 1;
41
        }
42
        cout << l << ' ';
43
    }
44
    cout << endl;
45
    for (int i = 2, j = 0; i <= n; ++i) {
46
        while (j && s[i] != s[j + 1]) j = ne[j];
47
        if (s[i] == s[j + 1]) j++;
48
        ne[i] = j;
49
    }
50
    for (int i = 1; i <= n; ++i) {
51
        cout << ne[i] << ' ';
52
    }
53
    cout << endl;
54
    return 0;
55
}

Inverse Suffix Array#

NOTE
这道题看了题解，刚学完一个新知识点上来就活用性质真的很难。

后缀数组就是一个字符串所有的后缀（根据第一个元素的位置编号）排序后的下标序列，是一个排列，这道题让根据已有的后缀数组构造出一个序列。首先按照后缀数组 sa 的顺序字符大小单调不减，只需要考虑什么时候有可能会变大。我们顺着 sa 的顺序填，假设当前需要填第 i 个，上一个填的是 c

当前面存在一个 j 使得， $inv(sa(i) + 1) < inv(sa(j) + 1) \land s(sa(j)) = c$ ，形象化的理解就是你后面有一个前缀一样的，现在你不改你的字典序就比之前填的小了，这是不允许的.
$sa(i) = n$ ，相当于上一个的边界情况

开线段树维护一下区间 max。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 100010;
5
int sa[N], inv[N], n;
6
char tr[N * 4], s[N];
7

8
void modify(int u, int l, int r, int p, char v) {
9
    if (l == r) tr[u] = v;
10
    else {
11
        int mid = l + r >> 1;
12
        if (p <= mid) modify(u << 1, l, mid, p, v);
13
        else modify(u << 1 | 1, mid + 1, r, p, v);
14
        tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
15
    }
16
}
17

18
char query(int u, int l, int r, int ql, int qr) {
19
    if (ql > qr) return 0;
20
    else if (ql <= l && r <= qr) return tr[u];
21
    else {
22
        int mid = l + r >> 1;
23
        char res = 0;
24
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
25
        if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
26
        return res;
27
    }
28
}
29

30
int main() {
31
    ios::sync_with_stdio(0);
32
    cin.tie(0), cout.tie(0);
33
    char cur = 'a';
34
    cin >> n;
35
    for (int i = 1; i <= n; ++i) cin >> sa[i], inv[sa[i]] = i;
36
    for (int i = 1; i <= n; ++i) {
37
        if (sa[i] == n) {
38
            if (i != 1) cur++;
39
            s[sa[i]] = cur;
40
            continue;
41
        }
42
        else cur = max(cur, char(query(1, 1, n, inv[sa[i] + 1], n) + 1));
43
        if (cur > 'z') {
44
            cout << -1 << endl;
45
            return 0;
46
        }
47
        s[sa[i]] = cur;
48
        modify(1, 1, n, inv[sa[i] + 1], s[sa[i]]);
49
    }
50
    cout << (s + 1) << endl;
51
    return 0;
52
}

String Transform#

Substring Order I#

涉及到子串，又是后缀自动机。在后缀自动机上沿着拓扑逆序 DP（可以用记搜）统计如果走某一条边能让位次增大多少，有了这个值之后一步一步模拟就能得到目标子串了。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 200010;
7
int last = 1, tot = 1;
8
struct Node {
9
    int len, fa;
10
    int ch[26];
11
} node[N];
12
LL cnt[N];
13

14
void extend(int c) {
15
    int p = last, np = last = ++tot;
16
    node[np].len = node[p].len + 1;
17
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
18
    if (!p) node[np].fa = 1;
19
    else {
20
        int q = node[p].ch[c];
21
        if (node[q].len == node[p].len + 1) node[np].fa = q;
22
        else {
23
            int nq = ++tot;
24
            node[nq] = node[q], node[nq].len = node[p].len + 1;
25
            node[q].fa = node[np].fa = nq;
26
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
27
        }
28
    }
29
}
30

31
void dfs(int x) {
32
    if (cnt[x]) return;
33
    cnt[x] = 1;
34
    for (int i = 0; i < 26; ++i) {
35
        if (node[x].ch[i]) dfs(node[x].ch[i]);
36
        cnt[x] += cnt[node[x].ch[i]];
37
    }
38
}
39

40
int main() {
41
    ios::sync_with_stdio(0);
42
    cin.tie(0), cout.tie(0);
43
    LL k;
44
    string s;
45
    cin >> s >> k;
46
    for (char c : s) extend(c - 'a');
47
    dfs(1);
48
    int cur = 1;
49
    while (k) {
50
        for (int i = 0; i < 26; ++i) {
51
            if (k > cnt[node[cur].ch[i]]) k -= cnt[node[cur].ch[i]];
52
            else {
53
                cout << char(i + 'a');
54
                k--;
55
                cur = node[cur].ch[i];
56
                break;
57
            }
58
        }
59
    }
60
    cout << endl;
61
    return 0;
62
}

Substring Order II#

除了需要统计重复的子串的个数之外，和上道题基本上完全一样。需要注意一些细节，我直接复制粘贴代码然后把 k 减成负的了导致死循环 OLE😭

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 200010;
7
int last = 1, tot = 1;
8
struct Node {
9
    int len, fa;
10
    int ch[26];
11
} node[N];
12
LL cnt[N], f[N];
13
int head[N], ne[N], ver[N], idx;
14

15
void add(int x, int y) {
16
    ver[++idx] = y;
17
    ne[idx] = head[x];
18
    head[x] = idx;
19
}
20

21
void extend(int c) {
22
    int p = last, np = last = ++tot;
23
    node[np].len = node[p].len + 1;
24
    f[np] = 1;
25
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
26
    if (!p) node[np].fa = 1;
27
    else {
28
        int q = node[p].ch[c];
29
        if (node[q].len == node[p].len + 1) node[np].fa = q;
30
        else {
31
            int nq = ++tot;
32
            node[nq] = node[q], node[nq].len = node[p].len + 1;
33
            node[q].fa = node[np].fa = nq;
34
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
35
        }
36
    }
37
}
38

39
void dfs1(int x) {
40
    for (int i = head[x]; i; i = ne[i]) {
41
        dfs1(ver[i]);
42
        f[x] += f[ver[i]];
43
    }
44
}
45

46
void dfs(int x) {
47
    if (cnt[x]) return;
48
    cnt[x] = f[x];
49
    for (int i = 0; i < 26; ++i) {
50
        if (node[x].ch[i]) dfs(node[x].ch[i]);
51
        cnt[x] += cnt[node[x].ch[i]];
52
    }
53
}
54

55
int main() {
56
    ios::sync_with_stdio(0);
57
    cin.tie(0), cout.tie(0);
58
    LL k;
59
    string s;
60
    cin >> s >> k;
61
    for (char c : s) extend(c - 'a');
62
    for (int i = 2; i <= tot; ++i) add(node[i].fa, i);
63
    dfs1(1);
64
    dfs(1);
65
    int cur = 1;
66
    while (k > 0) {
67
        for (int i = 0; i < 26; ++i) {
68
            if (k > cnt[node[cur].ch[i]]) k -= cnt[node[cur].ch[i]];
69
            else {
70
                cout << char(i + 'a');
71
                k -= f[node[cur].ch[i]];
72
                cur = node[cur].ch[i];
73
                break;
74
            }
75
        }
76
    }
77
    cout << endl;
78
    return 0;
79
}

Substring Distribution#

同样是后缀自动机的板子，每个结点 $i$ 能贡献长度为 $\left[len(fa(i)) + 1, len(i)]\right$ distinct sucstring 各一个，维护差分数组，最后前缀和输出。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 200010;
7
int last = 1, tot = 1;
8
struct Node {
9
    int len, fa;
10
    int ch[26];
11
} node[N];
12
LL a[N];
13

14
void extend(int c) {
15
    int p = last, np = last = ++tot;
16
    node[np].len = node[p].len + 1;
17
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
18
    if (!p) node[np].fa = 1;
19
    else {
20
        int q = node[p].ch[c];
21
        if (node[q].len == node[p].len + 1) node[np].fa = q;
22
        else {
23
            int nq = ++tot;
24
            node[nq] = node[q], node[nq].len = node[p].len + 1;
25
            node[q].fa = node[np].fa = nq;
26
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
27
        }
28
    }
29
}
30

31
int main() {
32
    ios::sync_with_stdio(0);
33
    cin.tie(0), cout.tie(0);
34
    string s;
35
    cin >> s;
36
    for (char c : s) extend(c - 'a');
37
    for (int i = 2; i <= tot; ++i) {
38
        a[node[node[i].fa].len + 1]++, a[node[i].len + 1]--;
39
    }
40
    for (int i = 1; i <= s.length(); ++i) {
41
        a[i] += a[i - 1];
42
        cout << a[i] << ' ';
43
    }
44
    cout << endl;
45
    return 0;
46
}

Star's Blog

Word Combinations#

String Matching#

Finding Borders#

Finding Periods#

Minimal Rotation#

Longest Palindrome#

Required Substring#

Palindrome Queries#

Finding Patterns#

Counting Patterns#

Pattern Positions#

Distinct Substrings#

Distinct Subsequences#

Repeating Substring#

String Functions#

Inverse Suffix Array#

String Transform#

Substring Order I#

Substring Order II#

Substring Distribution#