You Are Given Some Strings...(CF-1202E)(AC自动机)

题目

CF

思路

我们发现如果每次枚举拼接是 $O(n^2)?O(n^3)$ 的
于是我们可以采用 $AC$ 自动机来解决，处理出对于位置 $i$ 以它为后缀/前缀的 $s$ 数量然后乘法原理
用这种方法自顶向下递推即可

for(int i=1;i<=ncnt;i++)cnt[Q[i]]=cnt[Fail[Q[i]]]+cnt[Q[i]];

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
#define Setsize 26
#define MAXS 200000
#define MAXN 200000
#define INF 0x3f3f3f3f
struct Trie{
    int ncnt,Root,Fail[MAXN+5],nxt[MAXN+5][26],cnt[MAXN+5];void Init(){
    ncnt=-1,Root=Newnode();return ;}int Newnode(){
    ncnt++,cnt[ncnt]=0,Fail[ncnt]=0;memset(nxt[ncnt],0,sizeof(nxt[ncnt]));return ncnt;}void Insert(char *s){
    int u=Root,len=strlen(s);for(int i=0,j=s[i]-'a';i<len;i++,j=s[i]-'a'){
    if(!nxt[u][j])nxt[u][j]=Newnode();u=nxt[u][j];}cnt[u]++;return ;}int Q[MAXN+5],hed,tal,sum[MAXN+5];void Build(){
    hed=1,tal=0;for(int j=0;j<Setsize;j++)if(nxt[Root][j])Fail[nxt[Root][j]]=Root,Q[++tal]=nxt[Root][j];while(hed<=tal){
    int u=Q[hed++];for(int j=0;j<Setsize;j++){
    if(nxt[u][j])Fail[nxt[u][j]]=nxt[Fail[u]][j],Q[++tal]=nxt[u][j];else nxt[u][j]=nxt[Fail[u]][j];}}//for(int i=1;i<=ncnt;i++)// printf("%d ",cnt[i]);puts("");for(int i=1;i<=ncnt;i++)cnt[Q[i]]=cnt[Fail[Q[i]]]+cnt[Q[i]];//printf("%d ",cnt[Q[i]]);puts("");return ;}void Query(char *s){
    int u=Root,len=strlen(s);for(int i=0,j=s[i]-'a';i<len;i++,j=s[i]-'a')u=nxt[u][j],sum[i]=cnt[u];//printf("%d ",sum[i]);!!!//puts("");return ;}
}Front,Back;
char Re[MAXN+5],S[MAXN+5];
int main(){
    scanf("%s",Re);Front.Init(),Back.Init();int n=read();for(int i=1;i<=n;i++){
    scanf("%s",S);Front.Insert(S);int len=strlen(S);reverse(S,S+len);Back.Insert(S);}Front.Build(),Back.Build();Front.Query(Re);int len=strlen(Re);reverse(Re,Re+len);Back.Query(Re);LL ans=0;for(int i=1;i<len;i++)ans+=1ll*Front.sum[i-1]*Back.sum[len-i-1];printf("%lld\n",ans);return 0;
}

思考

当需要用到几个功能大致相同的统一数据结构时可以采用 $struct$ 减少码量，增加代码清晰度，而封装时采用 $namespace$ 好看
对于AC自动机能解决的问题注意积累经验