http://codeforces.com/gym/102428

G – Gluing Pictures

 

题意:给定一个字符串 S,多次询问,每次给定一个字符串 T,要用最少数量的 S 中的子串拼出串 T。问最少数量。

后缀自动机

后缀自动机是在压缩后缀。同一点上的字符串为后缀关系且出现位置最右点的集合相同,父节点是子节点的后缀,且子节点的出现位置集合是父节点的真子集。

首先要看出贪心,尽量长地匹配。

le 用于记录当前维护的连续的 S 中子串的长度。则每次 dp[i]=dp[ile]+1dp[i]=dp[i-le]+1

如果当前节点有字符 c 的边,则直接在后缀自动机上跳这条边,同时 le+1,表明这个子串仍在延长。

否则压缩后缀,即跳parent树的 fa 边,直到有字符 c 的边。同时 le 变为这一点代表的endpos等价类中最长串长度+1,再跳 字符 c 的边。要注意不能先跳,因为跳完之后的点上的最长串可能不是 T 以当前位置为右端点的子串,而眺之前所在的点上的最长串一定是 T 以当前位置为右端点的子串。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
struct node
{
int ch[26];
int len, fa;
}point[N << 1];
int las = 1, tot = 1;
void ins(int c){
int p = las;
int np = las = ++tot;
point[np].len = point[p].len + 1;
for (; p && !point[p].ch[c]; p = point[p].fa) point[p].ch[c] = np;
if (!p) point[np].fa = 1;
else{
int q = point[p].ch[c];
if (point[q].len == point[p].len + 1) point[np].fa = q;
else{
int nq = ++tot;
point[nq] = point[q];
point[nq].len = point[p].len + 1;
point[q].fa = point[np].fa = nq;
for (; p && point[p].ch[c] == q; p = point[p].fa) point[p].ch[c] = nq;
}
}
}
char s[N], t[N];
int q, n;
int dp[N];
int solve() {
n = strlen(t + 1);
int u = 1, le = 0;
for (int i = 1; i <= n; i++) {
int c = t[i] - 'A';
if (point[u].ch[c]) {
u = point[u].ch[c];
le++;
}
else {
while (u && !point[u].ch[c]) {
u = point[u].fa;
}
if (!u)return -1;
le = point[u].len + 1;
u = point[u].ch[c];
}
dp[i] = dp[i - le] + 1;
}
return dp[n];
}
int main() {
scanf("%s", s + 1);
for (int i = 1; s[i]; i++) {
ins(s[i] - 'A');
}
scanf("%d", &q);
while (q--) {
scanf("%s", t + 1);
printf("%d\n", solve());
}
return 0;
}