http://codeforces.com/gym/102428
G – Gluing Pictures
题意:给定一个字符串 S,多次询问,每次给定一个字符串 T,要用最少数量的 S 中的子串拼出串 T。问最少数量。
后缀自动机
后缀自动机是在压缩后缀。同一点上的字符串为后缀关系且出现位置最右点的集合相同,父节点是子节点的后缀,且子节点的出现位置集合是父节点的真子集。
首先要看出贪心,尽量长地匹配。
le 用于记录当前维护的连续的 S 中子串的长度。则每次 dp[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; }
|