详细题解

一、问题转化

设 $s = xyz$，其中 $x, y, z$ 是字符串，$y$ 非空。记 $|x| = a$，$|y| = l$，$|z| = n - a - l$，则 $a \ge 0$，$l \ge 1$，$a + l \le n$。
条件 $t = x y^k z$ 给出长度关系：

$$m = a + k l + (n - a - l) = n + (k-1)l \quad\Longrightarrow\quad (k-1)l = m - n. $$

因此 $l$ 必须整除 $m-n$，且 $k = \frac{m-n}{l} + 1 \ge 2$。

二、必要的位置限制

记 $L$ 为 $s$ 与 $t$ 的最长公共前缀长度：

$$L = \max\{i \mid s[1..i] = t[1..i]\},\quad 0\le L\le n. $$

由于 $x$ 和 $y$ 构成 $t$ 的前缀，必须有 $a+l \le L$，即 $b = a+l \le L$。

记 $suf$ 为 $s$ 与 $t$ 从末尾对齐的最长公共后缀长度：

$$suf = \max\{j \mid s[n-j+1..n] = t[m-j+1..m]\},\quad 0\le suf\le n. $$

因为 $z$ 必须等于 $t$ 的后缀，故 $|z| = n - b \le suf$，即 $b \ge n - suf$。

此外，从题解的分析可知，对于固定的 $l$，所有可能的 $b$ 构成一个连续区间，其左端点为 $b_{\min} = n - suf + l$，右端点为 $L$。因此只需检查 $b = b_{\min}$ 是否合法，若合法则整个区间 $[b_{\min}, L]$ 内的 $b$ 都对应合法三元组，贡献为 $L - b_{\min} + 1$；否则贡献为 $0$。

三、合法性验证

对于给定的 $l$ 和 $b = b_{\min}$，计算 $a = b - l$，$k = \frac{m-n}{l}+1$。需要验证：

$$t[a+1 .. a+kl] = \underbrace{y y \cdots y}_{k\text{ 次}},\quad \text{其中 } y = s[a+1 .. b]. $$

这可以通过字符串哈希快速完成。预处理 $s$ 和 $t$ 的哈希值（双模数防碰撞），则 $y$ 的哈希可 $O(1)$ 获得，$y$ 重复 $k$ 次的哈希为：

$$H(y^k) = H(y) \cdot \frac{P^{kl} - 1}{P^l - 1} \pmod{MOD}, $$

其中 $P$ 为哈希基数。利用预处理的幂次数组可 $O(1)$ 计算。

四、算法步骤

1. 读入 $n, m, s, t$。
2. 计算最长公共前缀长度 $L$。
3. 计算最长公共后缀长度 $suf$。
4. 若 $L = 0$，输出 $0$。
5. 令 $d = m - n$，枚举 $d$ 的所有正因子 $l$ 且 $l \le n$。
6. 对每个 $l$：
   • 计算 $b = n - suf + l$。
   • 若 $b > L$，跳过。
   • 计算 $a = b - l$，$k = d/l + 1$。
   • 用哈希验证 $t[a..a+kl-1]$ 是否等于 $s[a..b-1]$ 重复 $k$ 次。
   • 若通过，答案增加 $L - b + 1$。
7. 输出答案。

时间复杂度 $O(\sqrt{m-n} + \text{因子个数})$，实际接近 $O(\sqrt{m})$，完全可行。
注意 $n, m$ 最大 $10^7$，哈希预处理需 $O(m)$ 时间和 $O(m)$ 内存，在 $1024\text{MB}$ 限制内可接受。

---

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int BASE = 91138233;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

struct DoubleHash {
    vector<int> pre1, pre2, pow1, pow2;
    int n;

    DoubleHash(const string& s) {
        n = s.size();
        pre1.resize(n + 1);
        pre2.resize(n + 1);
        pow1.resize(n + 1);
        pow2.resize(n + 1);
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i <= n; ++i) {
            pow1[i] = (ll)pow1[i - 1] * BASE % MOD1;
            pow2[i] = (ll)pow2[i - 1] * BASE % MOD2;
        }
        for (int i = 0; i < n; ++i) {
            int v = s[i] - 'a' + 1;
            pre1[i + 1] = ((ll)pre1[i] * BASE + v) % MOD1;
            pre2[i + 1] = ((ll)pre2[i] * BASE + v) % MOD2;
        }
    }

    pair<int, int> get(int l, int r) const { // 0-indexed, inclusive
        int h1 = (pre1[r + 1] - (ll)pre1[l] * pow1[r - l + 1] % MOD1 + MOD1) % MOD1;
        int h2 = (pre2[r + 1] - (ll)pre2[l] * pow2[r - l + 1] % MOD2 + MOD2) % MOD2;
        return {h1, h2};
    }

    // 返回长度为 len 的子串重复 k 次的哈希（子串起点为 l）
    pair<int, int> repeat_hash(int l, int len, int k) const {
        auto h = get(l, l + len - 1);
        int h1 = h.first, h2 = h.second;
        int p1 = pow1[len], p2 = pow2[len];

        auto geom = [&](int p, int k, int mod) -> int {
            if (p == 1) return k % mod;
            // (p^k - 1) / (p - 1)
            int pk = (len * k <= n) ? pow1[len * k] : pow2[len * k]; // 注意这里需要根据 mod 选择，实际分开写
            // 为了清晰，分开处理
            return 0; // 下面会重写
        };
        // 分别计算两个模数下的几何级数和
        int sum1, sum2;
        if (p1 == 1) sum1 = k % MOD1;
        else {
            int pk1 = pow1[len * k];
            int inv = modinv(p1 - 1, MOD1);
            sum1 = (ll)(pk1 - 1 + MOD1) % MOD1 * inv % MOD1;
        }
        if (p2 == 1) sum2 = k % MOD2;
        else {
            int pk2 = pow2[len * k];
            int inv = modinv(p2 - 1, MOD2);
            sum2 = (ll)(pk2 - 1 + MOD2) % MOD2 * inv % MOD2;
        }
        int res1 = (ll)h1 * sum1 % MOD1;
        int res2 = (ll)h2 * sum2 % MOD2;
        return {res1, res2};
    }

private:
    int modinv(int a, int mod) const {
        int b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= mod;
        if (u < 0) u += mod;
        return u;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;

    // 最长公共前缀
    int L = 0;
    while (L < n && L < m && s[L] == t[L]) ++L;

    // 最长公共后缀
    int suf = 0;
    while (suf < n && suf < m && s[n - 1 - suf] == t[m - 1 - suf]) ++suf;

    if (L == 0) {
        cout << "0\n";
        return 0;
    }

    DoubleHash hs(s), ht(t);
    int diff = m - n;
    vector<int> factors;
    for (int l = 1; l * l <= diff; ++l) {
        if (diff % l == 0) {
            if (l <= n) factors.push_back(l);
            int other = diff / l;
            if (other != l && other <= n) factors.push_back(other);
        }
    }

    ll ans = 0;
    for (int l : factors) {
        int b = n - suf + l;
        if (b < 1 || b > L) continue;
        int a = b - l;
        if (a < 0) continue;
        int k = diff / l + 1;
        // 验证 t[a .. a+k*l-1] 是否等于 s[a .. b-1] 重复 k 次
        auto hash_y = hs.get(a, b - 1);
        auto hash_t = ht.repeat_hash(a, l, k);
        if (hash_y == hash_t) {
            ans += (L - b + 1);
        }
    }
    cout << ans << '\n';

    return 0;
}

---