Problem Jong Hyok and String
题目大意
给你n个字符串，有q个询问。
定义set(s)={(i,j)} 表示 s在第i个字符串中出现，且末尾位置为j。
对于一个询问，求set(Qi)=set(t) ，t的数量。
（n,q<=10^5 , 字符串总长<=10^5）
解题分析
直接将n个串塞进一个后缀自动机里面。
对于一个询问串qi，找到其在后缀自动机中出现的位置j。
则答案为len[j] - len[fail[j]] 。 （具体为什么还需要好好斟酌一下）
参考程序
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define V 100008
int ans[V];
struct sam{
int nt[V*][],f[V*],a[V*],rig[V*];
int last,sum,len;
int p,q,np,nq; void clear(){
memset(f,-,sizeof(f));
memset(a,,sizeof(a));
memset(nt,-,sizeof(nt));
last = sum = len=;
}
void insert(int ch){
len++;
if (~nt[last][ch] && a[nt[last][ch]]==len){
last=nt[last][ch]; return;
}
p=last; last=np=++sum; a[np]=a[p]+; rig[np]=;
for (;~p && !~nt[p][ch];p=f[p]) nt[p][ch]=np;
if (p==-) f[np]=;
else
{
q=nt[p][ch];
if (a[q]==a[p]+) f[np]=q;
else
{
nq=++sum; a[nq]=a[p]+;
memcpy(nt[nq],nt[q],sizeof(nt[q]));
f[nq]=f[q];
f[q]=f[np]=nq;
for (;~p && nt[p][ch]==q;p=f[p]) nt[p][ch]=nq;
}
}
}
int work(char *s,int l){
int now=;
for (int i=;i<=l;i++){
if (nt[now][s[i]-'a']==-) return ;
now=nt[now][s[i]-'a'];
}
return a[now]-a[f[now]];
}
}sam; char str[V];
void work(){
sam.clear();
int n,m;
scanf("%d %d",&n,&m);
for (int i=;i<=n;i++){
sam.len=sam.last=;
scanf("%s",str+);
int len=strlen(str+);
for (int j=;j<=len;j++) sam.insert(str[j]-'a');
}
for (int i=;i<=m;i++){
scanf("%s",str+);
int len=strlen(str+);
printf("%d\n",sam.work(str,len));
}
} int main(){
int T;
scanf("%d",&T);
for (int t=;t<=T;t++){
printf("Case #%d:\n",t );
work();
}
return ;
}