BZOJ-2780 Sevenk Love Oimaster(广义后缀自动机)

BZOJ-2780 Sevenk Love Oimaster(广义后缀自动机)

题目链接

题意

给出n个字符串,询问m个串一共出现在几个字符串中.

题解

广义后缀自动机板子题

将n个串建在一起,每次插入新的字符串时回到根节点

字符串如果出现在另一个字符串中,一定可以在后缀自动机上匹配到,而且在后缀自动机中就是某一个后缀的前缀即一个节点的后缀(slink)

建完广义后缀自动机之后,把n个串出现的节点标记,然后拿m个串分别在后缀自动机上匹配即可

其他

感觉这道题也能用后缀数组写,对每个询问求出它Sa的最长区间,然后离线用树状数组维护区间不同数字,复杂度因该是$nlogn$但是一直TLE…

#include <bits/stdc++.h> const int maxn = 5e5 + 5; using namespace std; struct SAM{ int trans[maxn<<1][26], slink[maxn<<1], maxlen[maxn<<1]; int cnt[maxn], vis[maxn]; int last, now, root, len; void init() { now = last = root = 1; } void newnode (int v) { maxlen[++now] = v; } void extend (int c) { newnode(maxlen[last]+1); int p = last, np = now; while (p && !trans[p][c]) { trans[p][c] = np; p = slink[p]; } if (!p) slink[np] = root; else { int q = trans[p][c]; if (maxlen[p] + 1 != maxlen[q]) { newnode(maxlen[p] + 1); int nq = now; memcpy(trans[nq], trans[q], sizeof(trans[q])); slink[nq] = slink[q]; slink[q] = slink[np] = nq; while (p && trans[p][c] == q) { trans[p][c] = nq; p = slink[p]; } }else slink[np] = q; } last = np; } void build(char *s) { len = strlen(s); last = 1; for (int i = 0; i < len; ++i) extend(s[i] - 'a'); } void init(char *s, int l, int r, int num) { int tnow = 1; for (int i = l; i < r; ++i) { tnow = trans[tnow][s[i] - 'a']; int tmp = tnow; while (tmp && vis[tmp] != num) { vis[tmp] = num; cnt[tmp]++; tmp = slink[tmp]; } } } int solve(char *s) { int tlen = strlen(s); int tnow = 1; for (int i = 0; i < tlen; ++i) tnow = trans[tnow][s[i] - 'a']; return cnt[tnow]; } }sam; char s[maxn]; int l[maxn], r[maxn]; int main() { int now = 0; int n, m; sam.init(); scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { l[i] = now; scanf("%s", s+now); sam.build(s+now); now = strlen(s); r[i] = now; } for (int i = 1; i <= n; ++i) { sam.init(s, l[i], r[i], i); } for (int i = 0; i < m; ++i) { scanf("%s", s); printf("%d\n", sam.solve(s)); } return 0; }