自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:49:45，当前版本为作者最后更新于2023-07-10 20:24:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

昨天晚上看到室友在玩一个叫千恋万花的游戏，中间忘了，现在我才认清我室友自私自利的嘴脸，根本不值得我给他分享好东西。

一句话题意：求字符串 $s$ 删去每个区间后字符串 $t$ 出现的次数之和。

下文字符串下标从零开始编号。

删去一个区间等价于取一个前缀 $pre$ 和一个后缀 $suf$，满足 $|pre|+|suf|<|s|$。$t$ 在 $pre$ 或 $suf$ 内部的情况是 trivial 的，我们可以一遍字符串匹配处理掉，考虑 $t$ 横跨两边的情况。

考虑枚举 $t$ 的哪一部分在 $pre$ 中，设这一部分为 $t_{0..i}$，则我们求出所有 $s$ 中匹配 $t_{0..i}$ 的左端点，设为 $A_i$，求出所有匹配 $t_{i+1..|t|-1}$ 的右端点，设为 $B_i$，则对答案的贡献为 $\sum\limits_{x \in A_i,y \in B_i}[y-x \ge |t|]$。

乍一看 $\sum |A_i|$ 和 $\sum |B_i|$ 都是 $O(n^2)$ 级别的，似乎没有什么高效算法，但是我们注意到 $\forall i < j, A_j \subseteq A_i, B_i \subseteq B_j$，于是我们考虑只记录 $A_i$ 和 $B_i$ 在 $i$ 增加时发生的变化，可以发现总变化量是 $O(n)$ 的，这样只要维护变化就可以维护出每个时候的 $A_i$ 和 $B_i$，然后每次 $A_i$ 和 $B_i$ 变化时，$\sum\limits_{x \in A_i,y \in B_i}[y-x \ge |t|]$ 的改变可以用一个树状数组统计。

考虑怎么维护 $A_i$ 和 $B_i$ 的变化，我们对于每个 $s$ 中的位置可以二分加哈希求出以这个位置为左端点能匹配的 $t$ 的最长长度，这样就可以维护出 $A_i$ 的变化，类似地，可以维护出 $B_i$ 的变化。

总复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int bas = 256, mod = 1e9 + 7;
int n, m;
string s, t;
int hasS[400005], hasT[400005];
int basPw[400005];
int GetHashS(int l, int r) { return (hasS[r] - 1ll * hasS[l - 1] * basPw[r - l + 1] % mod + mod) % mod; }
int GetHashT(int l, int r) { return (hasT[r] - 1ll * hasT[l - 1] * basPw[r - l + 1] % mod + mod) % mod; }
vector<int> lcg[400005], rcg[400005];
struct BIT {
    ll f[400005];
    void Modify(int i, int x) {
        for (; i <= n; i += i & -i) f[i] += x;
    }
    ll Query(int l, int r) {
        if (r < l) return 0;
        ll res = 0; l--;
        for (; r; r &= r - 1) res += f[r];
        for (; l; l &= l - 1) res -= f[l];
        return res;
    }
} tf, tg;
ll sum, ans;
void ModifyF(int i, int x) {
    tf.Modify(i, x);
    sum += tg.Query(1, max(i - m, 0)) * x;
}
void ModifyG(int i, int x) {
    tg.Modify(i, x);
    sum += tf.Query(min(i + m, n + 1), n) * x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> s >> t;
    n = s.length(); m = t.length(); s = '$' + s; t = '$' + t;
    for (int i = 1; i <= n; i++) hasS[i] = (1ll * hasS[i - 1] * bas + s[i]) % mod;
    for (int i = 1; i <= m; i++) hasT[i] = (1ll * hasT[i - 1] * bas + t[i]) % mod;
    basPw[0] = 1;
    for (int i = 1; i <= max(n, m); i++) basPw[i] = 1ll * basPw[i - 1] * bas % mod;
    for (int i = 1; i <= n; i++) {
        int l = 1, r = min(m, n - i + 1), res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (GetHashS(i, i + mid - 1) == GetHashT(1, mid)) {
                res = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        lcg[res].emplace_back(i);
    }
    for (int i = 1; i <= n; i++) {
        int l = 1, r = min(m, i), res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (GetHashS(i - mid + 1, i) == GetHashT(m - mid + 1, m)) {
                res = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        rcg[m - res + 1].emplace_back(i);
    }
    for (int i = 0; i <= m; i++) for (int j : lcg[i]) ModifyG(j, 1);
    for (int i : rcg[1]) ModifyF(i, 1);
    for (int i = 1; i < m; i++) {
        for (int j : lcg[i - 1]) ModifyG(j, -1);
        for (int j : rcg[i + 1]) ModifyF(j, 1);
        ans += sum;
    }
    for (int i = 1; i <= n - m + 1; i++) {
        if (GetHashS(i, i + m - 1) == GetHashT(1, m)) {
            int x = i, y = i + m - 1;
            ans += 1ll * (n - y + 1) * (n - y) / 2;
            ans += 1ll * (x - 1) * x / 2;
        }
    }
    printf("%lld\n", ans);
    return 0;
}