对 (T) 的每个位置进行考虑。
设 (f_i) 表示以 (T) 的第 (i) 个位置结尾的字符串((S_k))的个数
设 (g_i) 表示以 (T') 的第 (n-i+1) 个位置结尾的字符串((S_k'))的个数(其中 (T') 表示 (T) 的反串,(S_k') 同理)。
这两个数组分别用 (S_k) 和 (S_k') 的 AC自动机求就行了。
然后答案就是 (sumlimits_{i=1}^{lent-1}f_i imes g_{i+1})。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=200009;
char t[N];
int n,lent;
struct AC_DFA
{
int ch[N][30],tot=1,End[N],fail[N],head[N],cnt,f[N];
struct Edge
{
int nxt,to;
}g[N*2];
void add(int from,int to)
{
g[++cnt].nxt=head[from];
g[cnt].to=to;
head[from]=cnt;
}
void Insert(char s[],int len)
{
int k=1;
for (int i=1;i<=len;i++)
{
int t=s[i]-'a';
if(!ch[k][t])
ch[k][t]=++tot;
k=ch[k][t];
}
End[k]++;
}
void build_DFA()
{
for (int i=0;i<26;i++)
ch[0][i]=1;
queue <int> q;
q.push(1);
while(!q.empty())
{
int x=q.front();q.pop();
for (int i=0;i<26;i++)
if(ch[x][i])
fail[ch[x][i]]=ch[fail[x]][i],
q.push(ch[x][i]);
else
ch[x][i]=ch[fail[x]][i];
}
}
void dfs(int x)
{
End[x]+=End[fail[x]];
for (int i=head[x];i;i=g[i].nxt)
dfs(g[i].to);
}
void work(char t[])
{
build_DFA();
for (int i=2;i<=tot;i++)
add(fail[i],i);
dfs(1);
int k=1;
for (int i=1;i<=lent;i++)
{
int tmp=t[i]-'a';
k=ch[k][tmp];
f[i]=End[k];
}
}
}A,B;
void init()
{
scanf("%s",t+1);
lent=strlen(t+1);
scanf("%d",&n);
static char s[N];
for (int i=1;i<=n;i++)
{
scanf("%s",s+1);
int len=strlen(s+1);
A.Insert(s,len);
reverse(s+1,s+1+len);
B.Insert(s,len);
}
}
void work()
{
A.work(t);
reverse(t+1,t+1+lent);
B.work(t);
long long ans=0;
for (int i=1;i<lent;i++)
ans+=1ll*A.f[i]*B.f[lent-i];
printf("%lld
",ans);
}
int main()
{
init();
work();
return 0;
}