SP8093 JZPGYZ - Sevenk Love Oimaster 题解-白红宇

SP8093 JZPGYZ - Sevenk Love Oimaster 题解

阅读量：2305 次

发布时间：2019-05-09

本文共 2262 字，大约阅读时间需要 7 分钟。

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

题解

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

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

代码如下：

#include 
   
    #include 
    
     #include 
     #include 
      
       using namespace std;#define maxn 2000010int n,m;char s[maxn];struct state{
   	int len,link;	map
       
        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]);	}}

转载地址：http://ejnib.baihongyu.com/

你可能感兴趣的文章