题解 CF1202E 【You Are Given Some Strings...】

洛谷的$L^AT_EX$可能挂，请在[My blog](https://oierwanhong.cc/2020/04/18/CF1202E/)查看 ## CF1202E 题意：给一个串$T$和$n$个串$s_i$.定义$f(T,s)$表示$s$在$T$中的出现次数。 求$\sum_{i=1}^n\sum_{j=1}^nf(T,s_i+s_j)$. 数据范围：$|T|,\sum_{i=1}|s_i|\le 2\times 10^5$ <!--more--> 解：考虑枚举划分点$x$，该点及之前为$s_i$,该点之后为$s_j$,统计一下$s_i,s_j$的数量$f1(x),f2(x+1)$然后乘法原理相乘即可。 具体如何统计？该问题等价于，给一个文本串和一些模式串，要对文本串的每个前缀求出有多少模式串是他的后缀（后面那个只要把串反转就好） 文本串长度至多2e5,模式串长度和至多2e5. 对模式串建AC自动机，考虑fail指针指向的是根到当前串的最长后缀。而所求等价于为模式串的后缀的数量，因此通过fail求和即可。 时间复杂度为线性。 ``` #define MAXN 400011 struct ACAM { ll t[MAXN][26],val[MAXN],fail[MAXN],vis[MAXN];//val[u]表示点根到u的串的为模式串的后缀数量 ll cnt=0; void insert(char* a,ll n) { ll u=0; for(ll i=1;i<=n;++i) { ll &v=t[u][a[i]-'a']; if(!v)v=++cnt; u=v; } ++val[u]; } void build()//建AC自动机并求val { std::queue<ll>q; for(ll i=0;i<26;++i) if(t[0][i])q.push(t[0][i]); while(!q.empty()) { ll u=q.front();q.pop(); for(ll i=0;i<26;++i) { ll &v=t[u][i]; if(v)fail[v]=t[fail[u]][i],val[v]+=val[fail[v]],q.push(v); else v=t[fail[u]][i]; } } } void Query(char* a,ll n,ll f[])//求f { for(ll i=0;i<=cnt;++i)vis[i]=0; ll u=0; for(ll i=1;i<=n;++i) { u=t[u][a[i]-'a']; f[i]=val[u]; } } }ac,Rac;//ac自动机和反串的ac自动机 ll f1[MAXN],f2[MAXN]; char a[MAXN],b[MAXN]; int main() { scanf("%s",a+1); ll n=read(),la=strlen(a+1); while(n--) { scanf("%s",b+1); ll lb=strlen(b+1); ac.insert(b,lb);//插入ac自动机 std::reverse(b+1,b+lb+1);Rac.insert(b,lb); } ac.build();Rac.build(); ac.Query(a,la,f1);std::reverse(a+1,a+la+1);Rac.Query(a,la,f2); ll ans=0; for(ll i=1;i<=la;++i) { ans+=f1[i]*f2[la-i];//注意这里的f2没有反转，如果反转了就应该是f1[i]*f2[i+1] } printf("%lld",ans); return 0; } ```