hdu4416 Good Article Good sentence（多个串的本质不同的串个数，后缀自动机）

题意：

给定串S，和若干个串T(i)，
问有多少个S的本质不同的子串，在所有T(i)中没有出现过

数据范围：|S|<=1e5，,sum(|T|)<=1e5

解法：

将所有T串插入后缀自动机，计算出自动机中本质不同的串个数，记为cnt1，
然后将S串也插入后缀自动机，计算出自动机中本质不同的串个数，记为cnt2，
那么答案就是cnt2-cnt1，正确性显然。

多个串插入后缀自动机，插入这个串之前，将last置为根。

code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxm=2e6+5;
char s[maxm];
char t[maxm];
int n,m;
struct SAM{int ch[maxm][26];int fa[maxm],l[maxm];//l[]是等价类的最长字符串长度lenint last=1,tot=1;//tot是节点数量void add(int c){int p=last,np=++tot;last=np;l[np]=l[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{int q=ch[p][c];if(l[p]+1==l[q])fa[np]=q;else{int nq=++tot;l[nq]=l[p]+1;memcpy(ch[nq],ch[q],sizeof ch[q]);fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}}void init(){for(int i=1;i<=tot;i++){memset(ch[i],0,sizeof ch[i]);fa[i]=l[i]=0;}last=tot=1;}ll cal(){ll ans=0;for(int i=2;i<=tot;i++){ans+=l[i]-l[fa[i]];}return ans;}
}S;
signed main(){int T;cin>>T;int cas=1;while(T--){S.init();scanf("%d",&n);scanf("%s",s+1);for(int i=1;i<=n;i++){scanf("%s",t+1);int len=strlen(t+1);for(int j=1;j<=len;j++){S.add(t[j]-'a');}S.last=1;}ll cnt1=S.cal();int len=strlen(s+1);for(int i=1;i<=len;i++){S.add(s[i]-'a');}ll cnt2=S.cal();printf("Case %d: ",cas++);cout<<cnt2-cnt1<<endl;}return 0;
}