令$f(t,s)$为$s$在$t$中的出现次数

请计算$\sum_{i=1}^n\sum_{j=1}^nf(t,s_i+s_j)$。

枚举中间点即=$\sum_{i=1}^{n}L[i]\times R[i+1]$

一个正向$AC$，一个反向$AC$自动机即可。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

const int TS = 2e5 + 10;
struct ACAM
{
int scnt;
int nxt[N][26], fail[N];
ll cnt[N];
int root;
void init()
{
memset(nxt, 0, sizeof(nxt));
memset(cnt, 0, sizeof(cnt));
memset(fail, 0, sizeof(fail));
root = 0;
scnt = 0;
}
int Newnode()
{
int pos = ++scnt;
fail[pos] = 0;
memset(nxt[pos], 0, sizeof(nxt[pos]));
return pos;
}
void insert(char *t)
{
int len = strlen(t);
int tmp = root;
for (int i = 0; i < len; i++)
{
int id = t[i] - ‘a’;
if (!nxt[tmp][id])
nxt[tmp][id] = Newnode();
tmp = nxt[tmp][id];
}
cnt[tmp]++;
}
void build()
{
queue q;
for (int i = 0; i < 26; i++)
{
int tmp = nxt[root][i];
if (tmp)
{
q.push(tmp);
fail[tmp] = root;
}
}
while (!q.empty())
{
int x = q.front();
q.pop();
cnt[x] += cnt[fail[x]];
for (int i = 0; i < 26; i++)
{
int tmp = nxt[x][i];
if (tmp)
{
q.push(tmp);
fail[tmp] = nxt[fail[x]][i];
}
else
{
nxt[x][i] = nxt[fail[x]][i];
}
}
}
}
} T1, T2;

char s[N], t[N];
int n;
ll L[N], R[N];
int main()
{
scanf(“%s”, s);
scanf(“%d”, &n);
for (int i = 1; i <= n; i++)
{
scanf(“%s”, t);
T1.insert(t);
reverse(t, t + strlen(t));
T2.insert(t);
}
T1.build();
T2.build();
int slen = strlen(s);
int tmp = T1.root;
for (int i = 0; i < slen; i++)
{
int id = s[i] - ‘a’;
tmp = T1.nxt[tmp][id];
L[i] = T1.cnt[tmp];
}
tmp = T2.root;
for (int i = slen - 1; i >= 0; i—)
{
int id = s[i] - ‘a’;
tmp = T2.nxt[tmp][id];
R[i] = T2.cnt[tmp];
}
ll ans = 0;
for (int i = 0; i < slen - 1; i++)
{
ans += L[i] * R[i + 1];
}
printf(“%lld\n”, ans);
}