YZOJ P3897 Sevenk Love Oimaster
时间限制：1000MS 内存限制：131072KB
难度：\(7.5\)
-
题目描述
有 \(n\) 个大串和 \(q\) 个询问，每次给出一个字符串 \(s\) 询问在多少个大串中出现过。
-
输入格式
输入的第一行有两个整数分别代表 \(n\) 和 \(q\) 。
接下来的 \(n\) 行，分别给出题中所述的 n个只包含小写字母的字符串。
再接下来的 \(q\) 行，每行给出一个询问只包含小写字母的字符串。
-
输出格式
对于每一个询问，输出一行答案。
-
样例输入
|
1 2 3 4 5 6 7 |
3 3 abcabcabc aaa aafe abc a ca |
-
样例输出
|
1 2 3 |
1 3 1 |
-
数据规模与约定
\(n \leq 10000, q \leq 60000\) 。
原串总长度 \(\leq 100000\) 。
询问串总长度 \(\leq 360000\) 。
Source: BZOJ 2780 && SPOJ 8093
首先因为有多个模式串，所以建立一个广义SAM，并记录每个节点属于哪个串。
每个询问都在广义SAM上跑匹配，询问的答案就是最终匹配到的节点在 parent 树中的子树所包含的不同大串的数量。
显然可以在 parent 树上用
std::set 启发式合并，时间复杂度 \(O(nlog^2n)\) 。
或者按照 DFS序 离线用树状数组解决，时间复杂度 \(O(nlogn)\) 。
|
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 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <set> inline void getstr(char s[],int&ls) { register char c=0; while(!(c>='a' && c<='z')) c=getchar(); ls=0; while(c>='a' && c<='z') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } int gcnt,ghead[360505],gnext[750505],gnode[750505]; inline void insertLine(register int s,register int t) { gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t; gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s; } int cnt,parent[360505],mxval[360505],ch[360505][26]; inline int CreateNode(register int val=0) { parent[++cnt]=0,mxval[cnt]=val; for(register int j=0;j<26;j++) ch[cnt][j]=0; return cnt; } int root,last; inline int ExtendNode(register short c) { register int nw=CreateNode(mxval[last]+1),now=last; for(; now && !ch[now][c]; now=parent[now]) ch[now][c]=nw; if(!now) return parent[nw]=root,last=nw; register int q=ch[now][c]; if(mxval[q] == mxval[now]+1) return parent[nw]=q,last=nw; register int b=CreateNode(mxval[now]+1); parent[b]=parent[q],parent[nw]=parent[q]=b; for(register int j=0;j<26;j++) ch[b][j]=ch[q][j]; for(; now && ch[now][c]==q; now=parent[now]) ch[now][c]=b; return last=nw; } template<class T> inline void Merge(T&a,T&b) { if(a.size() < b.size()) a.swap(b); std::set<int>::iterator it=b.begin(); while(it != b.end()) a.insert(*it),it++; b.clear(); } int ans[360505]; std::set<int>apr[360001]; void DFS(register int o,register int fa) { for(register int j=ghead[o],t;j;j=gnext[j]) if((t=gnode[j]) != fa) { DFS(t,o); Merge(apr[o],apr[t]); } ans[o]=apr[o].size(); } char s[360505]; int main() { int N,Q;scanf("%d%d",&N,&Q); root=last=CreateNode(); for(register int lp=1;lp<=N;lp++) { int ls;getstr(s,ls); last=root; for(register int i=1;i<=ls;i++) { ExtendNode(s[i]-'a'); apr[last].insert(lp); } } for(register int i=2;i<=cnt;i++) insertLine(i,parent[i]); DFS(root,0); for(register int i=1;i<=Q;i++) { int ls;getstr(s,ls); register int now=root; for(register int i=1;i<=ls && now;i++) now=ch[now][s[i]-'a']; printf("%d\n",ans[now]); } return 0; } |