0%

串简单题选水

又开始做水题辣

bzoj 3942: 注意到没有一个串被另一个串完全包含是个很好的性质,如果没有就意味着按顺序匹配的话每匹配到一个就可以直接删掉。

那就维护一个栈来搞当前在哪里,然后直接在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
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

const int N = 100005;
int tr[N][26], fail[N], e[N], tot, n, pos[N], tp;
char s[N], t[N], st[N];
void Build(char* s) {
int u = 0;
for (int i = 1; s[i]; ++i) {
if (!tr[u][s[i] - 'a'])
tr[u][s[i] - 'a'] = ++tot;
u = tr[u][s[i] - 'a'];
}
e[u] = strlen(s + 1);
}
void Getfail() {
queue<int> q;
for (int i = 0; i < 26; ++i)
if (tr[0][i])
q.push(tr[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (tr[u][i])
fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
else
tr[u][i] = tr[fail[u]][i];
}
}
}
int main() {
scanf("%s", t + 1);
n = gi();
rep (i, 1, n) {
scanf ("%s", s + 1);
Build(s);
}
Getfail();
int m = strlen(t + 1), now = 0;
st[++tp] = ' ';
pos[tp] = now;
rep (i, 1, m) {
now = tr[now][t[i] - 'a'];
pos[++tp] = now;
st[tp] = t[i];
if (e[now]) {
assert(tp >= e[now]);
tp -= e[now];
now = pos[tp];
}
}
rep(i, 2, tp) putchar(st[i]);
return 0;
}

bzoj 4974:

首先用i-per[i]求出fail[i],并钦定第一个字符为a。

如果没跳到头肯定能知道这个字母是啥。如果跳到头了,那就mark一下已经被用过的字符,选一个最小的没被用到的填上。

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}
const int N = 1000010;
int n, per[N], fail[N], ans[N];
int main() {
n = gi();
rep (i, 1, n) per[i] = gi(), fail[i] = i - per[i];
ans[1] = 0;
rep (i, 2, n) {
if (fail[i])
ans[i] = ans[fail[i]];
else {
int pos = fail[i - 1];
vi used(26);
while (true) {
used[ans[pos + 1]] = 1;
if (!pos) break;
pos = fail[pos];
}
for (int j = 0; j < 26; ++j) if (!used[j]) {
ans[i] = j;
break;
}
}
}
rep(i, 1, n) putchar(ans[i] + 'a');
return 0;
}

poj2185

先把每行当做一个字符,把列最小周期求出来,再把列当做一个字符,求行的最小周期即可。

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

#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

const int N = 10000 + 5, M = 105;
char s[N][M];
int n, m, fail[N], sn, sm;
bool same(int l, int r) {
rep (i, 1, m) if (s[l][i] != s[r][i]) return 0;
return 1;
}
bool _same(int l, int r) {
rep (i, 1, sn) if (s[i][l] != s[i][r]) return 0;
return 1;
}
int main() {
n = gi(), m = gi();
rep (i, 1, n)
scanf("%s", s[i] + 1);
fail[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
while (j && !same(j + 1, i)) j = fail[j];
j += same(j + 1, i);
fail[i] = j;
}
sn = n - fail[n];
fail[1] = 0;
for (int i = 2, j = 0; i <= m; ++i) {
while (j && !_same(j + 1, i)) j = fail[j];
j += _same(j + 1, i);
fail[i] = j;
}
sm = m - fail[m];

cout << sn * sm << endl;
return 0;
}

hdu 6153:

很多人都用了exkmp做,其实并不用。

reverse一下s和t,变成尽可能的匹配t的前缀,而这正是kmp能维护的。每次在匹配的过程中,其实是不断地在fail树上做链加。因此直接搞个dfs树上差分一下就可以了。
哦,这题丧心病狂地把dfs卡爆栈了,那就利用i > fail[i]的概念倒着维护一遍就可以了。

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}
const int N = 1010101, MOD = 1e9 + 7;
int n, m, fail[N];
char s[N], t[N];
vi g[N];
int sum[N];
ll add(ll a, ll b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
void Sol() {
scanf("%s", (s + 1));
scanf("%s", (t + 1));
n = strlen(s + 1), m = strlen(t + 1);
std::reverse(s + 1, s + n + 1);
std::reverse(t + 1, t + m + 1);
rep(i, 0, m) g[i].clear(), sum[i] = 0;
fail[1] = 0;
g[0].push_back(1);
for (int i = 2, j = 0; i <= m; ++i) {
while (j && t[j + 1] != t[i])
j = fail[j];
j += (t[j + 1] == t[i]);
fail[i] = j;
g[fail[i]].push_back(i);
}
for (int i = 1, j = 0; i <= n; ++i) {
while (j && t[j + 1] != s[i]) j = fail[j];
j += (t[j + 1] == s[i]);
++sum[j];
if (j == m)
j = fail[j];
}
for (int i = m; i >= 0; i--) {
for (int j = 0; j < g[i].size(); j++)
sum[i] += sum[g[i][j]];
}
ll ans = 0;
rep(i, 1, m) ans = add(ans, 1ll * i * sum[i] % MOD);
cout << ans << '\n';
}
int main() {
int kase = gi();
while (kase--)
Sol();
return 0;
}

poj 3167

平常kmp的匹配是严格匹配,这里是只要离散化后相等就匹配。

这启发我们重新定义“匹配”的概念。在新加字符的时候,只要加进去之后排名相同就加。

这里面其实还是有fail的概念的。换句话说,只要这个匹配可以快速定义,那么就可以定义fail数组。

这个例子里可以主席树算一下排名。当然如果嫌麻烦可以写树状数组,复杂度是一样的。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

const int N = 100005;
struct persistent_segment_tree {
int rt[N], sum[N * 20], ls[N * 20], rs[N * 20], cnt;
persistent_segment_tree() {
memset(rt, 0, sizeof(rt));
memset(sum, 0, sizeof(sum));
memset(ls, 0, sizeof(ls));
memset(rs, 0, sizeof(rs));
cnt = 0;
}
void Update(int& p, int lst, int l, int r, int v) {
p = ++cnt;
ls[p] = ls[lst], rs[p] = rs[lst], sum[p] = sum[lst] + 1;
if (l == r) return;
int mid = (l + r) >> 1;
if(v <= mid) Update(ls[p], ls[lst], l, mid, v);
else
Update(rs[p], rs[lst], mid + 1, r, v);
}
int Qry(int p, int l, int r, int L, int R) {
if ((L <= l && r <= R) || !p)
return sum[p];
int mid = (l + r) >> 1, res = 0;
if (L <= mid)
res += Qry(ls[p], l, mid, L, R);
if (R > mid)
res += Qry(rs[p], mid + 1, r, L, R);
return res;
}
int Sm(int l, int r, int k) {
if (k == 1) return 0;
return Qry(rt[r], 1, 30, 1, k - 1) - Qry(rt[l - 1], 1, 30, 1, k - 1);
}
int Eq(int l, int r, int k) {
return Qry(rt[r], 1, 30, k, k) - Qry(rt[l - 1], 1, 30, k, k);
}
}aa, bb;
int n, k, s, a[N], b[N], fail[N];
int main() {
n = gi(), k = gi(), s = gi();
for (int i = 1; i <= n; ++i)
a[i] = gi(), aa.Update(aa.rt[i], aa.rt[i - 1], 1, 30, a[i]);
for (int i = 1; i <= k; ++i)
b[i] = gi(), bb.Update(bb.rt[i], bb.rt[i - 1], 1, 30, b[i]);
fail[1] = 0;
for (int i = 2, j = 0; i <= k; ++i) {
while (j && (!(bb.Sm(1, j, b[j + 1]) == bb.Sm(i - j, i - 1, b[i])) || !(bb.Eq(1, j, b[j + 1]) == bb.Eq(i - j, i - 1, b[i])))) j = fail[j];
j += ((bb.Sm(1, j, b[j + 1]) == bb.Sm(i - j, i - 1, b[i])) && (bb.Eq(1, j, b[j + 1]) == bb.Eq(i - j, i - 1, b[i])));
fail[i] = j;
}
vi answer;
for (int i = 1, j = 0; i <= n; ++i) {
while (j && (!(bb.Sm(1, j, b[j + 1]) == aa.Sm(i - j, i - 1, a[i])) || !(bb.Eq(1, j, b[j + 1]) == aa.Eq(i - j, i - 1, a[i])))) j = fail[j];
j += ((bb.Sm(1, j, b[j + 1]) == aa.Sm(i - j, i - 1, a[i])) && (bb.Eq(1, j, b[j + 1]) == aa.Eq(i - j, i - 1, a[i])));
if (j == k)
answer.push_back(i - k + 1), j = fail[j];
}
cout << answer.size() << endl;
for (int i = 0; i < answer.size(); i++)
printf ("%d\n", answer[i]);
return 0;
}

poj 4641

在上述过程中直接把维护个数改成维护pre[a[i]]即可。这个并不需要任何数据结构,只需要在vector上二分。

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

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

int C;

int abs(int x) {
return x >= 0 ? x : -x;
}
const int N = 1000005;
struct persistent_segment_tree {
vi store[N];
void Set() {
for (int i = 1; i <= C; ++i)
store[i].clear();
}

void insert(int x, int y) {
store[x].push_back(y);
}
int lst(int l, int r, int k) {
if (l > r)
return r - 10000000;
int l_ = 0, r_ = (int) store[k].size() - 1, ans = -1;
while (l_ <= r_) {
int mid = (l_ + r_) >> 1;
if (store[k][mid] <= r) ans = mid, l_ = mid + 1;
else r_ = mid - 1;
}
if (ans == -1 || store[k][ans] < l)
return r - 10000000;
else
return store[k][ans];
}
}aa, bb;
int n, k, a[N], b[N], fail[N];

void sol() {
n = gi(), k = gi();
aa.Set();
bb.Set();
for (int i = 1; i <= n; ++i)
a[i] = gi(), aa.insert(a[i], i);
for (int i = 1; i <= k; ++i)
b[i] = gi(), bb.insert(b[i], i);
fail[1] = 0;
for (int i = 2, j = 0; i <= k; ++i) {
while (j && !(abs(j + 1 - bb.lst(1, j, b[j + 1])) == abs(i - bb.lst(i - j, i - 1, b[i])))) j = fail[j];
j += (abs(j + 1 - bb.lst(1, j, b[j + 1])) == abs(i - bb.lst(i - j, i - 1, b[i])));
fail[i] = j;
}
// cout << "fail: ";
// for (int i = 1; i <= k; ++i) cout << fail[i] << " ";
// cout << '\n';
vi answer;
for (int i = 1, j = 0; i <= n; ++i) {
while (j && !(abs(j + 1 - bb.lst(1, j, b[j + 1])) == abs(i - aa.lst(i - j, i - 1, a[i])))) j = fail[j];
j += ((abs(j + 1 - bb.lst(1, j, b[j + 1])) == abs(i - aa.lst(i - j, i - 1, a[i]))));
if (j == k)
answer.push_back(i - k + 1), j = fail[j];
}
cout << answer.size() << endl;
for (int i = 0; i < (int)answer.size(); i++)
printf ("%d ", answer[i]);
cout << endl;
}
int main() {
int kase = gi();
C = gi();
while (kase--)
sol();
return 0;
}

bzoj 2938

先把AC自动机建出来,之后建图,每个fail链上有值的点都断掉,每个点向两种转移连边。

存在无限长的肯定意味着有一个环存在,那么拓扑排序判一下环即可。

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}
const int N = 100005;
struct AC_automaton {
int e[N], tr[N][2], fail[N], tot;

void insert(char* s) {
int now = 0;
for (int i = 1; s[i]; ++i) {
if (!tr[now][s[i] - '0'])
tr[now][s[i] - '0'] = ++tot;
now = tr[now][s[i] - '0'];
}
++e[now];
}

void Build() {
queue <int> q;
for (int i = 0; i < 2; i++)
if (tr[0][i]) q.push(tr[0][i]);
while (!q.empty()) {
int u = q.front();
e[u] += e[fail[u]];
q.pop();
for (int i = 0; i < 2; ++i) {
if (tr[u][i])
fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
else
tr[u][i] = tr[fail[u]][i];
}
}
}
}AC;
int n;
char s[N];
vi g[N];
int deg[N];
void toposort() {
queue<int> q;
int cnt = 0;
for (int i = 1; i <= AC.tot; ++i) if (!deg[i])
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
++cnt;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
--deg[v];
if (!deg[v])
q.push(v);
}
}
puts(cnt != AC.tot ? "TAK" : "NIE");
}
int main() {
n = gi();
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
AC.insert(s);
}
AC.Build();
for (int i = 1; i <= AC.tot; ++i) {
if (AC.e[i])
continue;
g[i].push_back(AC.tr[i][0]); ++deg[AC.tr[i][0]];
g[i].push_back(AC.tr[i][1]); ++deg[AC.tr[i][1]];
}

toposort();
return 0;
}

bzoj 3172: 每个字符串其实就是fail上的链加,跑一下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
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}
const int N = 1000000 + 5;
namespace AC {
int tr[N][26], e[N], fail[N], tot, sz[N];
vi g[N];
int Insert(char* s) {
int now = 0;
for (int i = 1; s[i]; ++i) {
if (!tr[now][s[i] - 'a']) tr[now][s[i] - 'a'] = ++tot;
now = tr[now][s[i] - 'a'];
++sz[now];
}
++e[now];
return now;
}
void Build() {
queue <int> q;
for (int i = 0; i < 26; ++i)
if (tr[0][i])
q.push(tr[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
g[fail[u]].push_back(u);
for (int i = 0; i < 26; i++) {
if (tr[u][i])
fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
else
tr[u][i] = tr[fail[u]][i];
}
}
}
void Run(char* t) {
int now = 0;
for (int i = 1; t[i]; ++i) {
now = tr[now][t[i] - 'a'];
++sz[now];
}
}
void dfs(int u) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
dfs(v);
sz[u] += sz[v];
}
}
}
int n, pos[N];
char s[N];
int main() {
n = gi();
rep (i, 1, n) {
scanf("%s", s + 1);
pos[i] = AC::Insert(s);
}
AC::Build();
AC::dfs(0);
rep (i, 1, n) cout << AC::sz[pos[i]] << endl;
return 0;
}

CF547E

AC自动机每走一步其实就是往fail树一条链上都添加了一个数id,于是就可以树上差分后线段树合并一下,来求出有多少个子树内的点覆盖了他。

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}
const int N = 200005;
int n, q;
int tr[N][26], fail[N], tot, rt[N], pos[N];
int ls[N * 40], rs[N * 40], sum[N * 40], cnt;
vi g[N];
char s[N];
int merge(int u, int v, int l, int r) {
if (!u || !v) return u + v;
int now = ++cnt;
sum[now] = sum[u] + sum[v];
int mid = (l + r) >> 1;
if (l == r) return now;
ls[now] = merge(ls[u], ls[v], l, mid);
rs[now] = merge(rs[u], rs[v], mid + 1, r);
return now;
}
void insert(int& p, int l, int r, int v) {
if (!p) p = ++cnt;
sum[p]++;
if (l == r)
return;
int mid = (l + r) >> 1;
if (v <= mid) insert(ls[p], l, mid, v);
else insert(rs[p], mid + 1, r, v);
}
int query(int p, int l, int r, int L, int R) {
if ((!p) || (L <= l && r <= R))
return sum[p];
int mid = (l + r) >> 1, res = 0;
if (L <= mid) res += query(ls[p], l, mid, L, R);
if (R > mid)
res += query(rs[p], mid + 1, r, L, R);
return res;
}
int Insert(char* s, int id) {
int now = 0;
for (int i = 1; s[i]; ++i) {
if (!tr[now][s[i] - 'a'])
tr[now][s[i] - 'a'] = ++tot;
now = tr[now][s[i] - 'a'];
insert(rt[now], 1, n, id);
}
return now;
}
void Build() {
queue <int> q;
for (int i = 0; i < 26; ++i)
if (tr[0][i])
q.push(tr[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (tr[u][i])
fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
else
tr[u][i] = tr[fail[u]][i];
}
}
}
void dfs(int u) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
dfs(v);
rt[u] = merge(rt[u], rt[v], 1, n);
}
}
int main() {
n = gi(), q = gi();
rep (i, 1, n) {
scanf("%s", s + 1);
pos[i] = Insert(s, i);
}
Build();
rep(i, 1, tot) g[fail[i]].push_back(i);
dfs(0);
while (q--) {
int l = gi(), r = gi(), k = gi();
printf("%d\n", query(rt[pos[k]], 1, n, l, r));
}
return 0;
}

hash killer:

rev(x): x每位取反

搞一个二进制串S(n) = S(n - 1) + rev(S(n - 1)),初始S(1) = 0

最后输出S(n)[i] + ‘a’即可,不写了

蚯蚓排队:暴力维护hash值即可,不写了