exkmp 求出 $a$ 的每个后缀和 $s$ 的 LCP，以及 $b$ 的每个后缀和 $s^r$ 的 LCP。
统计每个 $a_i$ 开头的方案数，two pointers 在 $b$ 上扫到对应的区间，树状数组维护即可。
设 $n,m$ 同阶，总时间复杂度 $\mathcal O(n \log n)$，$\log$ 在树状数组上而不在求 LCP 上，常数较小。
```cpp
const int N = 1e6 + 7;
int n, m, p[N], q[N], d[N], z[N];
ll c[N], ans;
char a[N], b[N], s[N];
inline void Z(char *s, int n) {
for (int i = 1; i <= n; i++) z[i] = 0;
z[1] = n;
for (int i = 2, l = 0, r = 0; i <= n; i++) {
if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
}
inline void exkmp(char *s, int n, char *t, int m, int *p) {
Z(t, m);
for (int i = 1; i <= n; i++) p[i] = 0;
for (int i = 1, l = 0, r = 0; i <= n; i++) {
if (i <= r) p[i] = min(z[i-l+1], r - i + 1);
while (i + p[i] <= n && s[i+p[i]] == t[p[i]+1]) ++p[i];
if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
}
}
inline void add(int x, int k) {
if (!x) return;
while (x <= m) c[x] += k, d[x] += k > 0 ? 1 : -1, x += x & -x;
}
inline pair<ll, int> ask(int x) {
ll k = 0;
int p = 0;
while (x) k += c[x], p += d[x], x -= x & -x;
return mp(k, p);
}
int main() {
rd(n), rd(m);
rds(a, n), rds(b, n), rds(s, m);
exkmp(a, n, s, m, p);
reverse(b + 1, b + n + 1);
reverse(s + 1, s + m + 1);
exkmp(b, n, s, m, q);
reverse(q + 1, q + n + 1);
for (int i = 1, j = 0; i <= n; i++) {
while (j + 1 <= n && j + 1 < i + m - 1) {
if (q[++j] == m) --q[j];
add(q[j], q[j]);
}
if (p[i] == m) --p[i];
pair<ll, int> x = ask(m), y = ask(m - p[i] - 1);
ans += x.fi - y.fi - 1ll * (x.se - y.se) * (m - p[i] - 1);
add(q[i], -q[i]);
}
print(ans);
return 0;
}
```