- 題意:給定一字串 S 和兩整數 M,L,對於任意一個長度為 ML 的子字串,將其切成 M 段長度 L 的小字串,如果這 M 段小字串相異,則我們說這個子字串為 “recoverable”,求 “recoverable” 字串數。
- 題解:做 L 次
silding window
,每次一開始把 M 段長度為 L 的字串 hash 值放入map
計數,之後增加右側一組字串,減去左邊一組字串,如果map.size()==M
,代表 M 段字串相異,”recoverable” 字串數 +1。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
73
74
75
using namespace std;
typedef unsigned long long ULL;
const int INF = 1e9;
const int MXN = 1e5 + 5;
const int MXV = 0;
const ULL MOD = 10009;
const ULL seed = 31;
cin.tie(NULL); \
cout.tie(NULL); \
ios_base::sync_with_stdio(false);
int m, L, sz;
ULL val[MXN], _pow[MXN];
char s[MXN];
ULL gethash(int L, int R) { return val[R] - val[L - 1] * _pow[R - L + 1]; }
map<ULL, int> mp;
int main()
{
_pow[0] = 1;
FOR(i, 1, MXN) { _pow[i] = _pow[i - 1] * seed; }
while (scanf("%d %d", &m, &L) != EOF)
{
scanf("%s", s + 1);
sz = strlen(s + 1);
val[0] = 0;
FOR(i, 1, sz + 1) { val[i] = val[i - 1] * seed + (s[i] - 'a'); }
int ans = 0;
for (int i = 1; i <= L && i + m * L <= sz; ++i)
{
// cout << i << ':' << '\n';
mp.clear();
for (int j = i; j < i + m * L; j += L)
{
ULL tmp = gethash(j, j + L - 1);
// cout << tmp << '\n';
mp[tmp]++;
}
if ((int)mp.size() == m)
{
++ans;
}
for (int j = i; j + m * L + L - 1 <= sz; j += L)
{
ULL tmp = gethash(j, j + L - 1);
--mp[tmp];
if (mp[tmp] == 0)
{
mp.erase(tmp);
}
++mp[gethash(j + m * L, j + m * L + L - 1)];
if ((int)mp.size() == m)
{
++ans;
}
}
}
cout << ans << '\n';
}
}
如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)