永久免费自动建站系统/今日国际新闻最新消息大事

题目传送门

题目大意： 给出 $n$ 个模板串以及 $m$ 个询问，每次询问一个串是多少个模板串的子串。

题解

显然直接建一个广义SAM，然后标记一下包含某个模板串前缀的状态属于哪个模板串，记为 $belong[i]$，那么问题变成了，询问时在广义SAM中找到这个串对应的状态，然后这个状态在后缀链接树中的子树中包含多少个不同的 $belong[i]$。

那么后面这个问题套一下dsu on tree的板子，预处理出每个节点的答案，询问的时候直接拿就好。

代码如下：

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 2000010int n,m;
char s[maxn];
struct state{int len,link;map<char,int>next;
}st[maxn];
int id=0,last,now,p,q;
int belong[maxn];
void extend(char x,int be)
{now=++id;st[now].len=st[last].len+1;belong[now]=be;for(p=last;p!=-1&&!st[p].next.count(x);p=st[p].link)st[p].next[x]=now;if(p!=-1){q=st[p].next[x];if(st[p].len+1==st[q].len)st[now].link=q;else{int clone=++id;st[clone]=st[q];st[clone].len=st[p].len+1;for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone;st[q].link=st[now].link=clone;}}last=now;
}
struct edge{int y,next;};
edge e[maxn];
int first[maxn],len=0;
void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;}
int size[maxn],mson[maxn];
void dfs1(int x)
{size[x]=1;for(int i=first[x];i;i=e[i].next){int y=e[i].y;dfs1(y);size[x]+=size[y];if(!mson[x]||size[y]>size[mson[x]])mson[x]=y;}
}
int ans[maxn],color[maxn],tot=0;
void add(int x){tot+=(!color[x]);color[x]++;}
void del(int x){color[x]--;tot-=(!color[x]);}
void go(int x,void (*func)(int x))
{if(belong[x])func(belong[x]);for(int i=first[x];i;i=e[i].next)go(e[i].y,func);
}
void dfs2(int x,bool v)
{for(int i=first[x];i;i=e[i].next)if(e[i].y!=mson[x])dfs2(e[i].y,false);if(mson[x])dfs2(mson[x],true);if(belong[x])add(belong[x]);for(int i=first[x];i;i=e[i].next)if(e[i].y!=mson[x])go(e[i].y,add);ans[x]=tot;if(!v)go(x,del);
}int main()
{scanf("%d %d",&n,&m);st[0].link=-1;for(int i=1,x;i<=n;i++){scanf("%s",s+1);x=strlen(s+1);last=0;for(int j=1;j<=x;j++)extend(s[j],i);}for(int i=1;i<=id;i++)buildroad(st[i].link,i);dfs1(0);dfs2(0,true);ans[0]=0;for(int i=1,x;i<=m;i++){scanf("%s",s+1);x=strlen(s+1);now=0;last=0;for(int j=1;j<=x;j++)if(st[now].next.count(s[j]))now=st[now].next[s[j]];else {last=1;break;}if(last)printf("0\n");else printf("%d\n",ans[now]);}
}