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
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 200010
#define Maxn 400010
#define maxm 5000010
#define ll long long
using namespace std;
int m;
char s[maxn], c[maxm];
struct SAM {
int sz, L, l, nxt[26];
} T[Maxn]; int f[Maxn], top, last, rt;
void init_SAM() {
for (int i = 0; i <= top; ++i) {
T[i].sz = T[i].L = T[i].l = f[i] = 0;
fill(T[i].nxt, T[i].nxt + 26, 0);
}
rt = last = top = 1;
T[rt].L = T[rt].l = T[rt].sz = f[rt] = 0;
}
void extend(int ch) {
int np = ++top, p = last; last = np;
T[np].L = T[p].L + 1; T[np].sz = 1;
while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
if (!p) return f[np] = rt, void();
int q = T[p].nxt[ch];
if (T[q].L - 1 == T[p].L) f[np] = q;
else {
int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
f[np] = f[q] = nq;
}
}
int tax[maxn], tp[Maxn];
void rsort(int n) {
for (int i = 1; i <= n; ++i) tax[i] = 0;
for (int i = 1; i <= top; ++i) ++tax[T[i].L];
for (int i = 1; i <= n; ++i) tax[i] += tax[i - 1];
for (int i = 1; i <= top; ++i) tp[tax[T[i].L]--] = i;
for (int i = top, u = tp[i]; i > 1; u = tp[--i]) {
T[f[u]].sz += T[u].sz;
}
}
void rebuild(int l, int r) {
init_SAM();
for (int i = l; i <= r; ++i) extend(s[i] - 'a');
if (l <= r) rsort(r - l + 1);
}
int bl[maxn];
void init_blo(int n) {
int blo = sqrt(n); blo = min(n, 9000);
for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
}
#define uint unsigned long long
struct Hash {
const int base = 13331;
int n;
uint pow[maxn], h[maxn];
void init(char *s) {
n = strlen(s + 1);
pow[0] = 1; for (int i = 1; i <= n; ++i) pow[i] = pow[i - 1] * base;
for (int i = 1; i <= n; ++i)
h[i] = s[i] + h[i - 1] * base;
}
void add(char ch) {
++n;
pow[n] = pow[n - 1] * base;
h[n] = ch + h[n - 1] * base;
}
uint get(int l, int r) { return h[r] - h[l - 1] * pow[r - l + 1]; }
uint hash(char *s) {
int l = strlen(s + 1); uint ans = 0;
for (int i = 1; i <= l; ++i)
ans = s[i] + ans * base;
return ans;
}
} H;
void work() {
cin >> s + 1 >> m;
int l = 1, r = strlen(s + 1), L, R, lans = 0;
init_blo(m); H.init(s);
for (int k = 1; k <= m; ++k) {
int opt; cin >> opt;
if (bl[k] != bl[k - 1]) L = l, R = r, rebuild(l, r);
if (opt == 1) {
cin >> c; c[0] = (c[0] - 'a' ^ lans) % 26 + 'a';
s[++r] = c[0]; s[r + 1] = 0;
H.add(s[r]);
} else if (opt == 2) {
++l;
} else {
cin >> c + 1;
int now = rt, len = strlen(c + 1), ans;
for (int i = 1; i <= len; ++i) c[i] = (c[i] - 'a' ^ lans) % 26 + 'a';
uint hv = H.hash(c);
for (int i = 1; i <= len; ++i) now = T[now].nxt[c[i] - 'a'];
ans = T[now].sz;
for (int i = L; i < l && i + len - 1 <= R; ++i)
if (H.get(i, i + len - 1) == hv) --ans;
for (int i = r; i > R && i - len + 1 >= l; --i)
if (H.get(i - len + 1, i) == hv) ++ans;
cout << (lans = ans) << "\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|