【bzoj2780】 Sevenk Love Oimaster

// 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;
}