链接

点击跳转

题解

把所有的串丢进AC自动机

AC自动机上的每个节点都有一个权值，这个权值代表“如果一个串匹配到这里，会对答案造成多大的贡献”

这个东西怎么算呢？

如果直接对fail链上的(深度 × \times ×经过这个点的串个数)求和，这样是会算重复的

比如 a a a a aaaa aaaa这个串扔进AC自动机，如果我拿 b a a a a baaaa baaaa来跑一下，匹配上的是前缀 a a a a aaaa aaaa，那么因为对fail链上求和，所以直接求出的贡献是 4 + 3 + 2 + 1 4+3+2+1 4+3+2+1，显然算多了很多，算多了 3 + 2 + 1 3+2+1 3+2+1，我只需要4就可以

那么我就差分，我对fail链上的((深度-next[深度]) × \times ×经过这个点的串个数)求和，就对了，这样相当于每次只增加一个增量

代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1500010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
ll c, f(1);
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
for(;isdigit(c);c=getchar())x=x*10+c-0x30;
return f*x;
}
struct KMP
{
int n, next[maxn], t[maxn];
void build(int *r, int len)
{
int i, j=0;
n=len;
for(i=1;i<=len;i++)t[i]=r[i];  t[len+1]=0;
for(i=2;i<=len;i++)
{
for(;j and t[j+1]!=t[i];j=next[j]);
next[i] = t[j+1]==t[i]?++j:0;
}
}
int move(int pos, int x)
{
for(;pos and t[pos+1]!=x;pos=next[pos]);
return t[pos+1]==x ? pos+1 : 0;
}
}kmp;
struct ACautomaton
{
int trie[maxn][30], tot, fail[maxn], tail[maxn];
ll w[maxn];
void clear()     //clear the arrays
{
for(int i=1;i<=tot;i++)cl(trie[i]), fail[i]=w[i]=tail[i]=0;
tot=1;
}
int insert(int *r, int len)     //insert a string into trie tree
{
kmp.build(r,len);
auto pos=1;
for(auto i=1;i<=len;i++)
{
pos = trie[pos][r[i]] ? trie[pos][r[i]] : trie[pos][r[i]]=++tot;
w[pos] += i-kmp.next[i];
}
tail[pos]++;
return pos;
}
void build()    //build the aca
{
queue<int> q;
int u, v, f;
q.push(1);
while(!q.empty())
{
u=q.front(); q.pop();
for(auto i=1;i<=26;i++)
if(trie[u][i])
{
v=trie[u][i];
for(f=fail[u];f and !trie[f][i];f=fail[f]);
fail[v] = f ? trie[f][i] : 1;
tail[v]+=tail[fail[v]];
w[v]+=w[fail[v]];
q.push(v);
}
}
}
int move(int pos, int c)
{
for(;pos and !trie[pos][c];pos=fail[pos]);
return pos ? trie[pos][c] : 1;
}
}aca;
int pos[maxn], len[maxn], r[maxn];
char s[maxn];
int main()
{
ll T=read();
while(T--)
{
ll ans=0, n=read(), i, j;
aca.clear();
len[0]=1;
rep(i,1,n)
{
pos[i] = pos[i-1] + len[i-1];
scanf("%s",s+pos[i]);
len[i] = strlen(s+pos[i]);
}
rep(i,1,pos[n]+len[n]-1)r[i]=s[i]-'a'+1;
rep(i,1,n)aca.insert(r+pos[i]-1,len[i]);
aca.build();
rep(i,1,n)
{
int p=1;
rep(j,0,len[i]-1)
p = aca.move(p,r[pos[i]+j]);
ans+=aca.w[p];
}
printf("%lld\n",ans);
}
return 0;
}

本文地址：https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/107344377