BZOJ2780(广义后缀自动机，set启发式合并)

BZOJ2780(广义后缀自动机，set启发式合并)

题面

自己找去

HINT

就是给多个文本串，然后每次查询的时候问你这个串在多少个文本串中出现过。因为多个文本串，那么直接就往广义后缀自动机上思考啊，我们在每个节点上开个set记录一下在哪些文本串上出现过，最后查询的时候就是看\(set[u].size()\)

启发式合并

因为每个父亲节点表示的子串都是儿子节点的后缀，所以儿子出现过的文本串，他爹也都出现过，那么就从叶子节点向上启发式合并就好了

#include<bits/stdc++.h>

#include<set>

using namespace std;

const int maxn=200010;

inline int read(){

    int w=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-') f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9'){

        w=(w<<3)+(w<<1)+ch-48;

        ch=getchar();

    }

    return w*f;

}

int n,m;

bool debug;

set<int> s[maxn];

set<int>::iterator it;

struct SUFFIXAUTOMATON{

	struct Node{

		int len,fa;

		map<int,int> ch;

	}node[200010];

	int lst,tot,root;

	inline void init(){

		lst=tot=root=1;return;

	}

	inline void extend(int now,int id){

		int p=lst;tot++;lst=tot;int np=tot;

		node[np].len=node[p].len+1;s[np].insert(id);

		while(p&&!node[p].ch[now]){

			node[p].ch[now]=np;

			p=node[p].fa;

		}

		if(!p) node[np].fa=1;

		else{

			int q=node[p].ch[now];

			if(node[q].len==node[p].len+1){

				node[np].fa=q;

			}

			else{

				int nq=++tot;node[nq]=node[q];

				node[nq].len=node[p].len+1;

				node[q].fa=nq;node[np].fa=nq;

				while(p&&node[p].ch[now]==q){

					node[p].ch[now]=nq;

					p=node[p].fa;

				}

			}

		}

	}

}SAM;

char ch[500010];

int head[200010],cnt;

struct Edge{

	int from,to,next;

}edge[1200010];

inline void addedge(int u,int v){

	cnt++;

	edge[cnt].from=u;

	edge[cnt].to=v;

	edge[cnt].next=head[u];

	head[u]=cnt;

}

int sum[200010];

inline void dfs(int u){

	if(debug)cout<<u<<endl;

	for(int i=head[u];i;i=edge[i].next){

		int v=edge[i].to;dfs(v);

		if(s[u].size()<s[v].size()) swap(s[u],s[v]);

		for(it=s[v].begin();it!=s[v].end();it++){

			s[u].insert(*it);

		}

	}

	sum[u]=s[u].size();return;

}

int main(){

	n=read();m=read();SAM.init();

	for(int i=1;i<=n;i++){

		scanf("%s",ch);int len=strlen(ch);

		for(int j=0;j<len;j++){

			SAM.extend(ch[j]-'a'+1,i);

		}

		SAM.lst=1;

	}

	for(int i=2;i<=SAM.tot;i++){

		addedge(SAM.node[i].fa,i);

	}

	dfs(1);

	for(int i=1;i<=m;i++){

		scanf("%s",ch);int len=strlen(ch);int u=SAM.root;

		for(int j=0;j<len;j++){

			u=SAM.node[u].ch[ch[j]-'a'+1];

		}

		printf("%d\n",sum[u]);

	}

	return 0;

}