HDU 4821 String 字符串哈希-白红宇

HDU 4821 String 字符串哈希

阅读量：5460 次

发布时间：2019-06-15

本文共 1495 字，大约阅读时间需要 4 分钟。

题意：

给一个字符串\(s\)，统计长为\(M*L\)的字串的个数。如果将该字串看成\(M\)个长为\(L\)的串拼接起来，那么这\(M\)个串必须互不相同。

分析：

枚举串的开头，然后用map来维护这\(M\)个hash值。

我用的《训练指南》上的hash方法：

定义一个\(H(n)=\sum{s_i x^{i-n}}\)

则\(i\)开头的长为\(L\)的字串的hash值为：\(H(i)-H(i+L)x^L\)

hash值为unsigned long long类型，这样就不用在代码中取模了。

#include 
    
     #include 
     
      #include 
      
       #include 
       using namespace std;const int maxl = 100000 + 10;char s[maxl];int n, M, L;const int x = 123;unsigned long long H[maxl], xp[maxl];map
        
          cnt;unsigned long long hashcode(int s, int L) {    return H[s] - H[s+L] * xp[L];}int main() {    xp[0] = 1;    for(int i = 1; i < maxl; i++) xp[i] = xp[i-1] * x;    while(scanf("%d%d", &M, &L) == 2) {        scanf("%s", s);        n = strlen(s);        H[n] = 0;        for(int i = n - 1; i >= 0; i--) H[i] = H[i+1] * x + s[i] - 'a';        long long ans = 0;        for(int s = 0; s + M * L <= n && s < L; s++) {            cnt.clear();            for(int i = s; i < s + L * M; i += L)                cnt[hashcode(i, L)]++;            if(cnt.size() == M) ans++;            for(int i = s + L * M; i + L <= n; i += L) {                int head = i - L * M;                unsigned long long p = hashcode(head, L);                if(cnt[p] == 1) cnt.erase(p);                else cnt[p]--;                cnt[hashcode(i, L)]++;                if(cnt.size() == M) ans++;            }        }        printf("%lld\n", ans);    }    return 0;}