【bzoj2780】 Sevenk Love Oimaster

http://www.lydsy.com/JudgeOnline/problem.php?id=2780 (题目链接)

题意

　　给出很多主串和很多询问串，求一个询问串在多少主串中出现过

Solution

　　我们先构造出后缀自动机，然后把主串在后缀自动机上匹配，能够到达哪个状态就把那个状态的计数器${cnts++}$，表示可以匹配到一个主串，同时，这个状态的后缀也可以被这个主串匹配到，所以我们还要跳${parent}$去更新它的祖先。有可能祖先会被重复计算，所以还要打个标记。。

　　最后询问串就在后缀自动机上跑匹配输出最终到达状态的计数器就好了。

细节

　　主串string存。

代码

// bzoj2780

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#define LL long long

#define inf (1ll<<30)

#define MOD 1000000007

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010,maxl=360010;

int par[maxn<<1],len[maxn<<1],cnts[maxn<<1],ch[maxn<<1][50];

int n,m,sz,Dargen,ww[maxn],id[maxn<<1],vis[maxn<<1];

char s[maxl];

string ss[maxn];

int Extend(int c,int p) {

	int np=++sz;

	len[np]=len[p]+1;

	for (;p && !ch[p][c];p=par[p]) ch[p][c]=np;

	if (!p) par[np]=Dargen;

	else {

		int q=ch[p][c];

		if (len[q]==len[p]+1) par[np]=q;

		else {

			int nq=++sz;len[nq]=len[p]+1;

			memcpy(ch[nq],ch[q],sizeof(ch[q]));

			par[nq]=par[q];

			par[np]=par[q]=nq;

			for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq;

		}

	}

	return np;

}

int match() {

	int l=strlen(s+1),p=1;

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

		if (!ch[p][s[i]-'a']) return 0;

		p=ch[p][s[i]-'a'];

	}

	return cnts[p];

}

int main() {

	scanf("%d%d",&n,&m);

	Dargen=sz=1;

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

		scanf("%s",s);

		ss[i]=(string)s;

		int l=ss[i].length(),p=1;

		for (int i=0;i<l;i++) p=Extend(s[i]-'a',p);

	}

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

		int l=ss[i].length(),p=1;

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

			p=ch[p][ss[i][j]-'a'];

			for (int k=p;k && vis[k]!=i;k=par[k]) cnts[k]++,vis[k]=i;

		}

	}

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

		scanf("%s",s+1);

		printf("%d\n",match());

	}

	return 0;

}