简单题

当字符串

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 里。

CPP

#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;
}

文章操作

相关推荐

评论

简单题