题解 CF1202E 【You Are Given Some Strings...】
万弘
2020-04-18 21:56:24
洛谷的$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;
}
```