HDU-4821

solution

字符串哈希

code

/*Siberian Squirrel*/
/*Cute JinFish*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1), eps = 1e-8;
/*const int MOD = 998244353, r = 119, k = 23, g = 3;
const int MOD = 1004535809, r = 479, k = 21, g = 3;*/
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const int M = 3e2 + 10, N = 1e5 + 10;
int sgn(double x) {
    if(fabs(x) < eps) return 0;
    return x < 0? -1: 1;
}
//inline int rnd(){static int seed=2333;return seed=(((seed*666666ll+20050818)%998244353)^1000000007)%1004535809;}
//double Rand() {return (double)rand() / RAND_MAX;}

ll n, m, l;
string s;
ull Hash[N], bin[N], base = 13331;
map<ull, int> mp;

ll quick_pow(ll ans, ll p, ll res = 1) {
    for(; p; p >>= 1, ans = ans * ans % MOD)
        if(p & 1) res = res * ans % MOD;
    return res % MOD;
}

void init() {
    bin[0] = 1;
    for(int i = 1; i < N; ++ i) {
        bin[i] = bin[i - 1] * base;
    }
}

ull get_sub(int l, int r) {
    return Hash[r] - Hash[l - 1] * bin[r - l + 1];
}

void solve(ll res = 0, ull temp = 0) {
    for(int i = 1; i <= l && i + m * l - 1 <= n; ++ i) {
        mp.clear();
        for(int j = i; j <= i + m * l - 1; j += l) {
            mp[get_sub(j, j + l - 1)] ++;
        }
        if(mp.size() == m) res ++;
        for(int j = i + m * l; j + l - 1 <= n; j += l) {
            temp = get_sub(j - m * l, j - m * l + l - 1);
            if(-- mp[temp] == 0) mp.erase(temp);
            mp[get_sub(j, j + l- 1)] ++;
            if(mp.size() == m) res ++;
        }
    }
    cout << res << endl;
}


int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
// srand(time(0));
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    init();
    int o = 1;
//	cin >> o;
    while(o --) {
        while(cin >> m >> l) {
            cin >> s; n = s.size();
            Hash[0] = 0;
            for(int i = 1; i <= n; ++i)
                Hash[i] = Hash[i - 1] * base + s[i - 1] - 'a';
            solve();
        }
    }
    return 0;
}