神刘家在走前体育课上问我听没听过 Die For You - The Weekend。我让他哼一段，刘家便展示了自己的天籁之音，我理所当然地连旋律都没辨认出来。
有的时候，对于一个完整的匹配串，我们需要「枚举断点」，分为前半段和后半段分别和模式串匹配解决问题。当然这样的技巧不止局限于字符串，我们在之前的学习中在诸如动态规划等题目中遇到了相似的情景。
在字符串题目中，一个典型的标志是「模式串的拼接」，将两截模式串拼接到一起，形成的新模式串并不利好我们的处理，我们需要尽量利用已知的模式串。当然我们不会将新模式串重新拆成两半，而是考虑转换，枚举匹配串的断点，将前半段的后缀和后半段的前缀分别匹配。
一个模板：CF1202E You Are Given Some Strings…
https://codeforces.com/problemset/problem/1202/E
虽然对于每种不同拼接需要求解分别的出现次数，但是注意到最后只需要输出 \(f\) 的总和，所以就可以不再顾及不同拼接方式间的区别。
枚举匹配串的断点。一个自然的想法是将前后缀与 AC 自动机匹配，但如果逐个放进去显然复杂度起飞。这里就又有一个实现小技巧，我们在原串的 AC 自动机上把原串过一遍，每个位置所在的状态就是这个位置对应后缀可能处在的后缀。
记录每个状态可能处在的模式串末尾个数，这一点直接在 fail 树上从上到下转移即可。反串同理。
二者相乘即为答案。
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
struct {
int T[maxn][26], tot, cnt[maxn], fail[maxn], deg[maxn];
void ins(std::string &t) {
int p = 0;
for (auto i : t) {
if (!T[p][i - 'a'])
T[p][i - 'a'] = ++tot;
p = T[p][i - 'a'];
}
++cnt[p];
return;
}
void bld(void) {
std::queue<int> q;
for (int i = 0; i < 26; ++i)
if (T[0][i])
q.push(T[0][i]);
for (; !q.empty(); ) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; ++i)
if (T[u][i]) {
int v = T[u][i];
fail[v] = T[fail[u]][i], cnt[v] += cnt[fail[v]];
q.push(v);
}
else
T[u][i] = T[fail[u]][i];
}
return;
}
} p, q;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
std::string s;
std::cin >> s;
int n;
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::string t;
std::cin >> t;
p.ins(t);
std::reverse(t.begin(), t.end());
q.ins(t);
}
p.bld(), q.bld();
int len = s.length();
std::vector<std::array<int, 2> > f(len + 1);
{
int u = 0;
for (int i = 1; i <= len; ++i) {
u = p.T[u][s[i - 1] - 'a'];
f[i][0] = p.cnt[u];
}
}
{
int u = 0;
for (int i = len; i; --i) {
u = q.T[u][s[i - 1] - 'a'];
f[i][1] = q.cnt[u];
}
}
long long res = 0ll;
for (int i = 1; i < len; ++i)
res += (long long)f[i][0] * f[i + 1][1];
std::cout << res << '\n';
return 0;
}