首先考虑转化为枚举分界点 \(i\)，令 \(f_i\) 表示 \(s_j\) 与 \(t_{[l, i]}\) 匹配的 \(j\) 的个数，\(g_i\) 表示 \(s_j\) 与 \(t_{[i, r]}\) 匹配的 \(j\) 的个数，则答案为 \(\sum f_i \times g_{i + 1}\)，\(f\) 的话，记一下其 fail 树上到根节点的作为某字符串结尾的节点的个数。\(g\) 的话考虑翻转一下 \(s, t\) 就变成了和求 \(f\) 一样的。时间复杂度 \(\mathcal{O}(n + m)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, f[N], g[N];
string s, t;
struct ACAM {int tot, son[N][26], fail[N], val[N];void insert(string s) {int u = 0;for (char c : s) {int &v = son[u][c - 'a'];if (!v) v = ++tot;u = v;}val[u]++;}void build() {queue<int>q;for (int i = 0; i < 26; i++) if (son[0][i]) q.push(son[0][i]);while (!q.empty()) {int u = q.front(); q.pop();for (int i = 0; i < 26; i++) {int &v = son[u][i];if (v) {fail[v] = son[fail[u]][i];val[v] += val[fail[v]];q.push(v);} else v = son[fail[u]][i];}}}void query(string s, int *f) {int u = 0;for (int i = 0; i < (int)s.size(); i++) {u = son[u][s[i] - 'a'];f[i] = val[u];}}
} acam1, acam2;
void main() {cin >> t;cin >> n;for (int i = 1; i <= n; i++) {cin >> s;acam1.insert(s);reverse(s.begin(), s.end());acam2.insert(s);}acam1.build(); acam2.build();acam1.query(t, f);reverse(t.begin(), t.end());acam2.query(t, g);ll ans = 0;int len = (int)t.size();for (int i = 0; i + 1 < len; i++) {ans += (ll)f[i] * g[len - i - 2];}cout << ans << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}
// start coding at 19:39
// finish debugging at 20:04