[广义后缀自动机] BZOJ2780 [Spoj]8093 Sevenk Love Oimaster

广义后缀自动机:

就是对若干个串,建成一个后缀自动机。

每次插入新串时从 \(1\) 开始。注意若 \(np\) 已经存在,需要考虑新建,具体看代码。

这题就是用广义后缀自动机建出 \(n\) 个串的后缀树。记下每个节点能匹配哪些串的子串。

问题转化成询问子树中有几种元素。

\(dfs\) 序转成区间之后,用HH的项链那种把贡献记在最后出现位置的套路即可。

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
#include<cstdio>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400005,maxe=maxn;
int N_sam,lst,par[maxn],Max[maxn];
map<int,int> ch[maxn];
set<int> S[maxn];
set<int>::iterator it;
int newnode(int t){
int p=++N_sam; par[p]=0; Max[p]=t;
ch[p].clear(); return p;
}
void Extend(int c,int id){
if(ch[lst][c]){
int np=ch[lst][c];
if(Max[np]==Max[lst]+1) lst=np; else{
int nnp=newnode(Max[lst]+1), p=lst;
ch[nnp]=ch[np];
par[nnp]=par[np]; par[np]=nnp;
while(p&&ch[p][c]==np) ch[p][c]=nnp, p=par[p];
lst=nnp;
}
} else{
int np=newnode(Max[lst]+1), p=lst;
while(p&&!ch[p][c]) ch[p][c]=np, p=par[p];
if(!p) par[np]=1; else{
int q=ch[p][c];
if(Max[q]==Max[p]+1) par[np]=q; else{
int nq=newnode(Max[p]+1);
ch[nq]=ch[q];
par[nq]=par[q]; par[q]=nq; par[np]=nq;
while(p&&ch[p][c]==q) ch[p][c]=nq, p=par[p];
}
}
lst=np;
}
S[lst].insert(id);
}
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int dfn[maxn],idfn[maxn],out[maxn],Tim;
void dfs(int x){
dfn[x]=++Tim; idfn[Tim]=x;
for(int j=fir[x];j;j=nxt[j]) dfs(son[j]);
out[x]=Tim;
}
int bit[maxn];
void Update(int x,int val){
for(;x<=N_sam;x+=(x&-x)) bit[x]+=val;
}
int Query(int x){
int res=0;
for(;x;x-=(x&-x)) res+=bit[x];
return res;
}
#define mp make_pair
#define X first
#define Y second
vector< pair<int,int> > q[maxn];
int ans[maxn];
int n,m,pos[maxn];
char st[maxn];
int main(){
freopen("bzoj2780.in","r",stdin);
freopen("bzoj2780.out","w",stdout);
scanf("%d%d",&n,&m);
newnode(0); lst=1;
for(int i=1;i<=n;i++){
scanf("%s",st); int len=strlen(st);
lst=1; for(int j=len-1;j>=0;j--) Extend(st[j],i);
}
for(int i=2;i<=N_sam;i++) add(par[i],i);
dfs(1);
for(int i=1;i<=m;i++){
scanf("%s",st); int len=strlen(st);
bool pd=true; int p=1;
for(int j=len-1;j>=0;j--)
if(!ch[p][st[j]]){ pd=false; break; } else p=ch[p][st[j]];
if(!pd) ans[i]=0; else q[out[p]].push_back(mp(dfn[p],i));
}
for(int i=1;i<=N_sam;i++){
for(it=S[idfn[i]].begin();it!=S[idfn[i]].end();it++){
if(pos[*it]) Update(pos[*it],-1);
Update(pos[*it]=i,1);
}
for(int j=0;j<q[i].size();j++){
int x=q[i][j].X,y=q[i][j].Y;
ans[y]=Query(i)-Query(x-1);
}
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}