题目描述
https://acm.hdu.edu.cn/showproblem.php?pid=7157
简要题意：给定一个长度为 $n$ 的模板串 $S$ 和一个空串 $T$，现在有 $m$ 次操作，操作有两种，第一种给定一个字符 $ch$ 和一个整数 $k$，表示在 $T$ 的后面加入 $k$ 个 $ch$；第二种操作给定一个整数 $k$，表示删掉 $T$ 末尾的 $k$ 个字符，问在操作的过程中，是否出现某一个时刻满足 $S$ 是 $T$ 的一个子串
$n,m\le 2\times 10^5,k\le 10^9$
Solution
我们考虑建出 $S$ 的 $nxt$ 树，我们的第一想法是对于每个点预处理加入 $2^k$ 个字符 $ch$ 后转移到哪个点，但是这样做的时间复杂度和空间复杂度都是 $O(26n\log k)$ 的
我们稍作思考可以发现，每个点只会有一个字符的成功转移，其它字符都会先不断跳 $nxt$ 直到一个可以成功转移的位置，那么我们对于每个点预处理每个字符不断跳 $nxt$ 的位置以及可以成功转移的字符跳 $2^k$ 步后所到达的位置即可
对于删除，我们维护一个栈，记录每次添加字符前所在的位置，每次暴力删除即可
时间复杂度 $O(n\log k)$
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
| #include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#define maxn 200010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;
int n, m;
char s[maxn];
int ch[maxn];
int nxt[maxn], f[maxn][30], g[maxn][26];
void init_nxt() {
nxt[1] = 0; int k = 0;
for (int i = 2; i <= n; ++i) {
while (k && s[k + 1] != s[i]) k = nxt[k];
if (s[k + 1] == s[i]) ++k;
nxt[i] = k;
}
for (int ch = 0; ch < 26; ++ch) g[n][ch] = n;
for (int i = 0; i < 30; ++i) f[n][i] = n;
for (int i = 0; i < 30; ++i) f[n + 1][i] = 0;
for (int i = 0; i < n; ++i) {
for (int ch = 0; ch < 26; ++ch) g[i][ch] = n + 1;
if (i > 0) for (int ch = 0; ch < 26; ++ch) g[i][ch] = g[nxt[i]][ch];
g[i][ch[i + 1]] = i; f[i][0] = i + 1;
}
for (int j = 1; j < 30; ++j)
for (int i = 0; i < n; ++i)
f[i][j] = f[g[f[i][j - 1]][ch[i + 1]]][j - 1];
}
int jump(int now, int ch, int k) {
for (int i = 0; i < 30; ++i) {
if (!(k >> i & 1)) continue;
now = f[g[now][ch]][i];
} return now;
}
struct node {
int now, ch, k;
};
void work() {
cin >> n >> m >> s + 1; bool ok = 0;
for (int i = 1; i <= n; ++i) ch[i] = s[i] - 'a';
init_nxt(); int now = 0; stack<node> S;
while (m--) {
char c[3]; int k, ch; cin >> c >> k; ch = c[0] - 'a';
if (c[0] != '-') {
S.push({ now, ch, k });
now = jump(now, ch, k);
if (now == n) ok = 1;
} else {
while (!S.empty() && k) {
node t = S.top(); S.pop();
if (k < t.k) {
now = jump(t.now, t.ch, t.k - k);
t.k -= k; k = 0; S.push(t); break;
}
k -= t.k; now = t.now;
}
}
}
cout << (ok ? "yes" : "no") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|