CF271D 【Good Substrings】

定义哈希函数 \(H(c)=\sum_{i = 1} ^ m c_i*b^{m-i}\)

\(H(C,K+1)=H(C,K)*b+C_{K+1}\)（K个坏字母）

用long long

#include<bits/stdc++.h>

using namespace std;

long long a[3000010], k, x, y, cnt;

char s[3000010], s1[300010];

int main(){

    scanf("%s%s%lld", s, s1, &k);

    for (long long i = 0;s[i]; i ++) {

		x = k, y = 0;

		for (long long j = i; s[j] && (s1[s[j] - 'a'] > '0' || x --); j ++)

			a[cnt ++] = y = (y * 131) ^ s[j];

	}

	sort(a, a + cnt);

	cnt = unique(a, a + cnt) - a;

	printf("%lld\n", cnt);

	return 0;

}

巴特西

CF271D 【Good Substrings】

用long long

最新文章

热门文章