E. You Are Given Some Strings...
AC自动机
求一个串$t$中包含子串$s_{i}+s_{j}$的个数。
可以正反跑两遍AC自动机
正着跑,表示$s_{i}$结束,反正跑对应$s_{i}$开头
#include<bits/stdc++.h> using namespace std; #define maxn 1000005 #define maxm 28 struct AC{ int trieN; int ch[maxn][maxm]; int val[maxn],tt[maxn]; int fail[maxn]; int sum[maxn]; vector<int> v; void init() { trieN=-1; newnod(); } int newnod() { memset(ch[++trieN],0,sizeof ch[0]); val[trieN]=fail[trieN]=0; return trieN; } void insert(const string & str) { int cur=0; for(int i=0;i<str.size();i++){ int d=str[i]-'a'; if(!ch[cur][d]){ ch[cur][d]=newnod(); } cur=ch[cur][d]; } val[cur]++; } void build() { queue<int> q; for(int i=0;i<maxm;i++){ if(ch[0][i]){ q.push(ch[0][i]); } } while(!q.empty()){ int cur=q.front(); v.push_back(cur); q.pop(); for(int i=0;i<maxm;i++){ if(ch[cur][i]){ fail[ch[cur][i]]=ch[fail[cur]][i]; q.push(ch[cur][i]); }else{ ch[cur][i]=ch[fail[cur]][i]; } } } for(int i=0;i<v.size();i++){ int u=v[i]; tt[u]=tt[fail[u]]+val[u]; }///优化?? } void query(const string & str) { int res=0,cur=0; for(int i=0;str[i];i++){ int d=str[i]-'a'; cur=ch[cur][d]; sum[i]=tt[cur]; res=0; } //return res; } }ac1,ac2; int main() { string s,t; cin>>t; int n; scanf("%d",&n); for(int i=0;i<n;i++){ cin>>s; ac1.insert(s); reverse(s.begin(),s.end()); ac2.insert(s); } ac1.build(); ac2.build(); ac1.query(t); long long ans=0; reverse(t.begin(),t.end()); ac2.query(t); int len=t.length(); /*for(int i=0;i<len;i++){ cout<<ac1.sum[i]<<" "<<ac2.sum[i]<<endl; }*/ // cout<<len<<'\n'; for(int i=1;i<=len;i++){ ans+=(long long)ac1.sum[i-1]*ac2.sum[len-i-1]; } cout<<ans<<'\n'; }