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

题意

Alice 可以从 s 中删除任意多个字符，但剩下的字符相对顺序不能变，所以她最后保留下来的一定是 s 的一个非空子序列。

Bob 只能删掉左边一段和右边一段，因此他最后保留下来的一定是 t 的一个非空连续子串。

题目要我们统计：有多少个不同的字符串，既能作为 s 的子序列出现，又能作为 t 的子串出现。

也就是说，本题可以等价改写成：

枚举 t 的所有非空子串；
只保留那些同时也是 s 的子序列的字符串；
最后对这些字符串去重计数。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

int n;
string s, t;

// 检查 need 是否能作为 s 的子序列。
bool is_subsequence(const string &need) {
    int p = 0;
    for (int i = 0; i < (int)s.size() && p < (int)need.size(); i++) {
        if (s[i] == need[p]) {
            p++;
        }
    }
    return p == (int)need.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s >> t;

    // brute.cpp：枚举 Bob 保留的所有子串，再判断它是否能由 Alice 作为子序列留下。
    // 复杂度较高，只适合小数据验证和对拍。
    set<string> answer;
    for (int l = 0; l < n; l++) {
        string cur = "";
        for (int r = l; r < n; r++) {
            cur.push_back(t[r]);
            if (is_subsequence(cur)) {
                answer.insert(cur);
            }
        }
    }

    cout << answer.size() << '\n';

    return 0;
}

朴素做法就是把 t 的所有子串都枚举出来，再逐个判断它是不是 s 的子序列，用 set 去重。这个思路完全正确，但子串有 $O(n^2)$ 个，每次判断子序列又要 $O(n)$ ，再加上字符串插入集合的开销，整体只能拿来做小数据验证。

关键是把“所有合法子串”换一种视角来看。

设 t[i..n] 是 t 的一个后缀。我们定义 max_len[i] 表示：这个后缀的最长前缀，有多长可以作为 s 的子序列。

那么从位置 i 开始，所有合法字符串就不是一堆零散的串，而是一个很整齐的集合：

长度为 1 的前缀合法；
长度为 2 的前缀合法；
…
一直到长度为 max_len[i] 的前缀都合法。

因为如果一个更长的前缀已经能作为子序列出现，那么它的更短前缀当然也能出现。

于是问题变成了：

对每个后缀 t[i..n]，它贡献了一段“前缀长度区间” 1..max_len[i]；
这些前缀字符串在不同后缀之间可能重复；
要把重复的部分扣掉。

第一步先求 max_len[i]。
我们对 s 建一个“子序列自动机” nxt_pos：nxt_pos[p][c] 表示在 s 中位置 p 之后，第一个字符 c 出现在哪里。这样从 t[i] 往右扫时，就能贪心地找到最早匹配位置，直到某个字符再也匹配不上为止，这样扫过的长度就是 max_len[i]。

第二步处理去重。
如果两个后缀 t[x..n] 和 t[y..n] 的最长公共前缀长度是 lcp(x,y)，那么这两个后缀前 lcp(x,y) 个前缀字符串完全一样。再结合 max_len[y]，就知道后缀 y 最多能帮后缀 x 覆盖掉多少长度：

min(max_len[y], lcp(x,y))

为了方便统计，我们把所有后缀按字典序排序。然后从小到大处理当前后缀 x，看它前面所有后缀里，最多已经覆盖了它前多少个前缀。设这个值为 cover，那么当前后缀新贡献的不同字符串个数就是：

max(0, max_len[x] - cover)

这里 cover 直接枚举前面所有后缀取最大值即可。因为 n <= 3000，做一个 $O(n^2)$ 的两层循环完全够用。

代码中的对应关系如下：

max_len[i]：后缀 t[i..n] 能取到的最长合法前缀长度；
lcp[i][j]：两个后缀的最长公共前缀；
sa[]：后缀起点按字典序排序后的结果；
枚举 sa[i] 时扫描前面的 sa[j]，求最大的覆盖长度 cover。

代码

cpp

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;

int n;
string s, t;

int nxt_pos[MAXN][26]; // nxt_pos[i][c] 表示在 s 中位置 i 之后，第一个字符 c 出现的位置
int max_len[MAXN];     // max_len[i] 表示后缀 t[i..n] 的最长前缀，有多长能作为 s 的子序列
int lcp[MAXN][MAXN];   // lcp[i][j] 表示后缀 t[i..n] 和 t[j..n] 的最长公共前缀长度
int sa[MAXN];          // 按字典序排序后的后缀起点

// 比较两个后缀 t[x..n] 和 t[y..n] 的字典序。
bool suffix_less(int x, int y) {
    if (x == y) {
        return false;
    }
    int same = lcp[x][y];
    int len_x = n - x + 1;
    int len_y = n - y + 1;
    if (same == len_x || same == len_y) {
        return len_x < len_y;
    }
    return t[x + same] < t[y + same];
}

// 构造 s 的子序列自动机。
void build_next_position() {
    for (int c = 0; c < 26; c++) {
        nxt_pos[n][c] = n + 1;
        nxt_pos[n + 1][c] = n + 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int c = 0; c < 26; c++) {
            nxt_pos[i][c] = nxt_pos[i + 1][c];
        }
        nxt_pos[i][s[i + 1] - 'a'] = i + 1;
    }
}

// 计算每个起点 i 能向右延伸多长，仍然可以作为 s 的子序列。
void build_max_len() {
    for (int i = 1; i <= n; i++) {
        int pos = 0;
        int len = 0;
        for (int j = i; j <= n; j++) {
            pos = nxt_pos[pos][t[j] - 'a'];
            if (pos == n + 1) {
                break;
            }
            len++;
        }
        max_len[i] = len;
    }
}

// 预处理任意两个后缀的 LCP。
void build_lcp() {
    for (int i = n; i >= 1; i--) {
        for (int j = n; j >= 1; j--) {
            if (t[i] == t[j]) {
                lcp[i][j] = lcp[i + 1][j + 1] + 1;
            }
            else {
                lcp[i][j] = 0;
            }
        }
    }
}

long long solve() {
    build_next_position();
    build_max_len();
    build_lcp();

    for (int i = 1; i <= n; i++) {
        sa[i] = i;
    }
    sort(sa + 1, sa + n + 1, suffix_less);

    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        int cur = sa[i];
        int cover = 0;
        for (int j = 1; j < i; j++) {
            int pre = sa[j];
            int same = lcp[cur][pre];
            if (same > max_len[pre]) {
                same = max_len[pre];
            }
            if (same > cover) {
                cover = same;
            }
        }
        if (max_len[cur] > cover) {
            answer += max_len[cur] - cover;
        }
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s >> t;
    s = " " + s;
    t = " " + t;

    cout << solve() << '\n';

    return 0;
}

复杂度

构造子序列自动机： $O(26n)$
计算全部 max_len[i]： $O(n^2)$
计算全部 lcp[i][j]： $O(n^2)$
后缀排序比较是 $O(1)$ 的，整体排序 $O(n log n)$
枚举每个后缀和前面所有后缀求覆盖： $O(n^2)$

所以总时间复杂度是 $O(n^2)$ ，空间复杂度是 $O(n^2)$ 。

总结

这题最关键的不是一上来想“怎么统计所有子串”，而是先把每个起点能产生的合法字符串整理成一个“前缀区间”。

一旦看出“后缀 + 最长合法前缀长度”这个模型，后面就只剩两个标准动作：

用子序列自动机求每个后缀能延伸多长；
用字典序和 LCP 处理不同后缀之间的重复部分。

所以这题本质上是一道字符串建模题：先把题意压缩成好数的对象，再去做去重计数。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

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

目录

题意

思路

代码

复杂度

总结

一图流解析