# bzoj 2780 [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.

3 3

abcabcabc

aaa

aafe

abc

a

ca

1

3

1

### 题解

n个串建个广义后缀自动机，注意建的时候对于每个点标记一下这个点有多少个串用了这个点，多个串的化就外挂一个链表。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
using namespace std;
struct Graph_Chain
{
struct edge
{
int to,next;
}e[N];
int st[N],tot;
{
e[++tot].next=st[x];
e[tot].to=y,st[x]=tot;
}
int dfn[N],dfs_id,pos[N],low[N];
void dfs(int now)
{
dfn[now]=++dfs_id,pos[dfs_id]=now;
for (int i=st[now];i;i=e[i].next)
dfs(e[i].to);
low[now]=dfs_id;
}
}g,chain;
{
int l,r,id;
{
return a.r<b.r;
}
struct SAM
{
int dis[N<<1],fa[N<<1],ch[N<<1][26],sz,root,last;
void init(){sz=1,root=1,last=root;}
void insert(int x,int t)
{
int now=ch[last][x],pre=last;
if (now)
if (dis[now]==dis[pre]+1) last=now;
else
{
int nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[now],sizeof ch[now]);
fa[nows]=fa[now],fa[now]=nows;
for (;pre && ch[pre][x]==now;pre=fa[pre]) ch[pre][x]=nows;
last=nows;
}
else
{
now=++sz,dis[now]=dis[pre]+1;last=now;
for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
if (!pre) fa[now]=root;
else if (dis[ch[pre][x]]==dis[pre]+1) fa[now]=ch[pre][x];
else
{
int q=ch[pre][x],nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[q],sizeof ch[nows]);
fa[nows]=fa[q],fa[q]=fa[now]=nows;
for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
}
}
}
void ins(char s[],int t)
{
int len=strlen(s+1);
last=root;
for (int i=1;i<=len;i++)
insert(s[i]-'a',t);
}
void match(char s[],int t)
{
int now=root,len=strlen(s+1);
for (int i=1;i<=len;i++)
if (ch[now][s[i]-'a'])
now=ch[now][s[i]-'a'];
else {now=0;break;}
}
}sam;
struct BIT
{
#define lowbit(x) (x&(-x))
int c[N];
{
if (!x) return;
for (;x<=sam.sz;x+=lowbit(x)) c[x]+=v;
}
int sum(int x)
{
int ans=0;
for (;x;x-=lowbit(x)) ans+=c[x];
return ans;
}
int query(int l,int r)
{
return sum(r)-sum(l-1);
}
#undef lowbit
}bit;
int ans[N],vis[N],n,m;
char s[360010];
main()
{
sam.init();
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%s",s+1),sam.ins(s,i);
for (int i=1;i<=sam.sz;i++)
g.dfs(1);
for (int i=1;i<=m;i++)
scanf("%s",s+1),sam.match(s,i);
int top;
for (int i=1;i<=sam.sz;i++)
{
int now=g.pos[i];
for (int j=chain.st[now];j;j=chain.e[j].next)
{
int v=chain.e[j].to;