首页 > 代码库 > 【BZOJ2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机

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

2024-10-13 03:02:03   217人阅读

【BZOJ2780】[Spoj]8093 Sevenk Love Oimaster

Description

     Oimaster and sevenk love each other.

    But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman‘s nature, sevenk felt angry and began to check oimaster‘s online talk with ChuYuXun.    Oimaster talked with ChuYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this,    "how many strings in oimaster‘s online talk contain this string as their substrings?"

Input

 There are two integers in the first line, the number of strings n and the number of questions q.And n lines follow, each of them is a string describing oimaster‘s online talk. And q lines follow, each of them is a question.n<=10000, q<=60000 the total length of n strings<=100000, the total length of q question strings<=360000 

Output

For each question, output the answer in one line.

Sample Input

3 3
abcabcabc
aaa
aafe
abc
a
ca

Sample Output

1
3
1

题意：给你一堆文本串，每次询问一个串在多少个文本串中出现过。

题解：多串匹配要用到广义SAM。就是在每当开始加入一个串的时候，将last指针变回root。

那么这题怎么搞？我们需要知道SAM中的每个节点被多少个文本串所包含。记录sum[i]表示i被多少个文本串包含，vis[i]表示当前时刻，最后一个包含i的文本串是哪个。在建完SAM后，我们将所有串在SAM上再跑一边，将经过的点，以及它的parent树上的所有祖先都更新一遍（因为一个点被影响后它的所有parent也要被影响），如果某个点的vis=当前时间，则退出，否则更新sum和vis。

时间复杂度我不太会证，大概O(nsqrt(n))吧？不过这题也有O(nlogn)的做法，就是求出parent树的DFS序，每次询问相当于问一个点在parent树的子树中有多少个不同的文本串，也就转换成在DFS序上的一段区间中有多少个不同的文本串。这个显然是HH的项链啊，不过感觉好麻烦。（懒）

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,m,tot;int pre[400010],ch[400010][26],mx[400010],s[400010],vis[400010],lp[400010],rp[400010];char str[800010];void updata(int x,int y){	for(;x&&vis[x]!=y;x=pre[x])	s[x]++,vis[x]=y;}int extend(int x,int y,int p){	int np=++tot;	mx[np]=mx[p]+1;	for(;p&&!ch[p][x];p=pre[p])	ch[p][x]=np;	if(!p)	pre[np]=1;	else	{		int q=ch[p][x];		if(mx[q]==mx[p]+1)	pre[np]=q;		else		{			int nq=++tot;			pre[nq]=pre[q],pre[np]=pre[q]=nq,mx[nq]=mx[p]+1;			memcpy(ch[nq],ch[q],sizeof(ch[q]));			for(;p&&ch[p][x]==q;p=pre[p])	ch[p][x]=nq;		}	}	return np;}int main(){	scanf("%d%d",&n,&m);	int i,j,a,b;	tot=1;	for(i=1;i<=n;i++)	{		lp[i]=rp[i-1];		scanf("%s",str+lp[i]);		rp[i]=strlen(str);		for(b=1,j=lp[i];j<rp[i];j++)	b=extend(str[j]-‘a‘,i,b);	}	for(i=1;i<=n;i++)		for(a=1,j=lp[i];j<rp[i];j++)	a=ch[a][str[j]-‘a‘],updata(a,i);	for(i=1;i<=m;i++)	{		scanf("%s",str);		a=strlen(str);		for(b=1,j=0;j<a;j++)		{			if(ch[b][str[j]-‘a‘])	b=ch[b][str[j]-‘a‘];			else	break;		}		if(j==a)	printf("%d\n",s[b]);		else	printf("0\n");	}	return 0;}

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


联系
我们