0%

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$

解:考虑枚举划分点$x$,该点及之前为$s_i$,该点之后为$s_j$,统计一下$s_i,s_j$的数量$f1(x),f2(x+1)$然后乘法原理相乘即可。

具体如何统计?该问题等价于,给一个文本串和一些模式串,要对文本串的每个前缀求出有多少模式串是他的后缀(后面那个只要把串反转就好)
文本串长度至多2e5,模式串长度和至多2e5.
对模式串建AC自动机,暴力跳fail的代码是这样的:

1
2
3
4
5
6
7
8
9
10
void Query(char* a,ll n,ll f[])//文本串是a,求f(f[i]表示有多少模式串是[1,i]这个前缀的后缀
{
ll u=0;
for(ll i=1;i<=n;++i)
{
u=t[u][a[i]-'a'];
ll v=u;
while(v)f[i]+=val[v],v=fail[v];//val[u]是以u结尾的模式串数量
}
}

这样时间复杂度是错的,最坏会达到$\mathcal O(|T|\times \sum|s_i|)$,比如一长串a。

记$u$通过跳fail得到的序列是$p_1,p_2,p_3,…p_k$,且$p1=u,fail(p_i)=p_i+1,p_k=0$

记$s(u)=\sum_{i=1}^k s(p_i)=s(fail(u))+val(u)$.这其实就类似前缀和。求fail的时候顺便求即可。找到$[1,i]$这个前缀在AC机上的点$u$ $,f(i)=s(u)$

时间复杂度为线性。(代码中$val(u)$表示$s(u)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}