HDOJ 4821

发表于 |

题目

给长度为N的字符串S，问长度为L×M的由M个长度为L的不同字符串连成的S的子串有多少个。

数据范围

$1 \leq M \times L \leq N \leq 105$

做法

枚举起点，用滑窗法计算答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 5;
const ll P = 23456789;
const ll MOD = 1e9 + 7;
// 这组质数会有Hash冲突
// const ll P = 9973;
// const ll MOD = 130003;
char s[MAX_N];
int M, L, N;
ll hsh[MAX_N];
ll pow_P[MAX_N];
map<ll, int> cnt;
inline ll GetHash(int l, int r)
{
  ll tmp = hsh[r] - hsh[l] * pow_P[r - l];
  tmp = (tmp % MOD + MOD) % MOD;
  return tmp;
}
int Calc(int start)
{
  int res = 0;
  int l = start, r = start + L;
  cnt.clear();
  for (; r <= N && r - l <= L * M; r += L) {
  // for (int l = start; l < start + M * L; l += L) {
    ++cnt[GetHash(r - L, r)];
    // ++cnt[GetHash(l, l + L)];
  }
  if ((int)cnt.size() == M) {
  // if (r - L - l == M * L && Check()) {
    ++res;
  }
  for (; r <= N; l += L, r += L) {
  // int p = start;
  // for (int l = start + M * L; l + L <= N; l += L) {
    int tmp_num = --cnt[GetHash(l, l + L)];
    if (tmp_num == 0) cnt.erase(GetHash(l, l + L));
    ++cnt[GetHash(r - L, r)];
    // int tmp_num = --cnt[GetHash(p, p + L)];
    // if (tmp_num == 0) cnt.erase(GetHash(p, p + L));
    // p += L;
    // ++cnt[GetHash(l, l + L)];
    if ((int)cnt.size() == M) {
      ++res;
    }
  }
  return res;
}
int main()
{
  pow_P[0] = 1;
  for (int i = 1; i < MAX_N; ++i) {
    pow_P[i] = pow_P[i - 1] * P % MOD;
  }
  while (scanf("%d%d", &M, &L) != EOF) {
    scanf("%s", s);
    N = strlen(s);
    hsh[0] = 0;
    for (int i = 1; i <= N; ++i) {
      hsh[i] = (hsh[i - 1] * P + s[i - 1]) % MOD;
    }
    int ans = 0;
    for (int i = 0; i < L; ++i) {
    // for (int i = 0; i < L && i + M * L <= N; ++i) {
      ans += Calc(i);
    }
    printf("%d\n", ans);
  }
  return 0;
}

总结

  1. Hash的基数和模数要取大素数，不然冲突的概率很大。
  2. 用Hash做题时，错误可能是代码写错了或者有Hash冲突。
  3. 循环的限制条件尽量写在最外层循环上，可以减少内层循环对合法性的判断。
  4. map去重很好用。