SP8093 Sevenk Love Oimaster 题解
题面
对 \(n\) 个串建广义 SAM，每个点开一棵线段树维护 parent 树子树内的所有点都被哪些串走到过。这个直接线段树合并即可。注意分裂出来的点也需要update（我也不知道为何，反正不update会WA）。
点击查看代码
const int N=5e5+13,M=5e5+13,logN=21;
int pcnt=0;
struct SegTree{int lson,rson,cnt;}t[N*logN];
#define ls t[p].lson
#define rs t[p].rson
#define mid ((l+r)>>1)
inline void refresh(int p){t[p].cnt=t[ls].cnt+t[rs].cnt;}
void update(int &p,int l,int r,int x){
if(!p) p=++pcnt;
if(l==r) return t[p].cnt=1,void();
x<=mid?update(ls,l,mid,x):update(rs,mid+1,r,x);
refresh(p);
}
void merge(int &p,int q,int l,int r){
if(!p||!q) return p|=q,void();
if(l==r) return t[p].cnt|=t[q].cnt,void();
merge(ls,t[q].lson,l,mid),merge(rs,t[q].rson,mid+1,r);
refresh(p);
}
char s[M];
int n,m,nxt[N<<1],len[N<<1],ptot=1,lastpos=1,rt[N<<1];
std::unordered_map son[N<<1],zrzak;
std::vector G[N<<1];
inline int newpos(std::unordered_map nson,int nlen){return len[++ptot]=nlen,std::swap(son[ptot],nson),ptot;}
inline void insert(int c,int op){
int p=lastpos,u=newpos(zrzak,len[p]+1);update(rt[u],1,n,op);
while(p&&son[p].find(c)==son[p].end()) son[p][c]=u,p=nxt[p];
lastpos=u;
if(!p) return nxt[u]=1,void();
int d=son[p][c];
if(len[d]==len[p]+1) nxt[u]=d;
else{
int v=newpos(son[d],len[p]+1);update(rt[v],1,n,op);
nxt[v]=nxt[d],nxt[u]=nxt[d]=v;
while(p&&son[p][c]==d) son[p][c]=v,p=nxt[p];
}
}
void dfs(int u){for(auto v:G[u]) dfs(v),merge(rt[u],rt[v],1,n);}
int main(){
read(n),read(m);
for(int i=1;i<=n;++i){
read(s+1);
int len=strlen(s+1);
for(int j=1;j<=len;++j) insert(s[j]-'a',i);
lastpos=1;
}
for(int i=2;i<=ptot;++i) G[nxt[i]].pb(i);
dfs(1);
while(m--){
read(s+1);int len=strlen(s+1),now=1;bool flag=1;
for(int i=1;i<=len;++i){
int c=s[i]-'a';
if(son[now].find(c)==son[now].end()){flag=0;break;}
now=son[now][c];
}
if(!flag) println(0);
else println(t[rt[now]].cnt);
}
return 0;
}