自动搬运

查看原文

来自洛谷，原作者为

	jiangxinyang2012 我常常追忆过去。

搬运于2025-08-24 23:08:35，当前版本为作者最后更新于2025-02-19 10:46:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

当字符串 $m$ 中所有字母出现的次数都和 $n$ 一致时，$m$ 一定是 $n$ 的一个排列。

所以，我们可以根据字符串 $n$ 中每个字母出现的数量来构造一个哈希函数：

$$h(x)=c_a \cdot base^{0}+c_b \cdot base^{1}+c_c \cdot base^{2}+\cdots+c_z \cdot base^{25} $$

其中，$c_x$ 表示字母 x 出现的次数。

这样，我们就可以枚举排列的最后一个位置，每次 $O(1)$ 更新子串哈希值，并和 $n$ 的哈希值对比，如果一样，再把排列的子串哈希值丢进 set 里。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
using ull = unsigned long long;
const ull base = 131;
char a[N], b[N];
ull pw[N], d[N];
ll f(int l, int r) {
    return d[r] - d[l - 1] * pw[r - l + 1];
}
int main() {
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    pw[0] = 1;
    for (int i = 1; i <= m; i++) {
        pw[i] = pw[i - 1] * base;
    }
    for (int i = 1; i <= m; i++) {
        d[i] = d[i - 1] * base + b[i] - 'a';
    }
    ll h = 0;
    for (int i = 1; i <= n; i++) {
        h += pw[a[i] - 'a'];
    }
    ll h2 = 0;
    set<ll> se;
    int tot = 0;
    for (int i = 1; i <= m; i++) {
        h2 += pw[b[i] - 'a'];
        if (i > n) h2 = h2 - pw[b[i - n] - 'a'];
        if (i >= n && h2 == h) {
            se.insert(f(i - n + 1, i));
        }
    }
    printf("%d\n", (int)se.size());
    return 0;
}