题解UVA10298 Power Strings
Kalium
·
·
个人记录
UVA10298 Power Strings题解
前置芝士：hash 的熟练操作
题意：
求串 A 最多是由几个子串 B 组成
思路：
明显我们可以一个个枚举，然后判断当前长度为 k 的 B 串是否拼的成
即判断 s[i + k - 1] - s[i - 1] * power[k] 是否等于 k
其中 s 即为 hash 数组，power_i 即为 base^i
由于本人是萌新
所以解释下为什么 * power[k]
很简单
举个栗子吧
```
len = 6, k = 2, i = 3
```
那么我们来看看
```
s[i + k - 1] = s[4]
即为
s[1] * base ^ 3 + s[2] * base ^ 2 + s[3] * base + s[4]
```
```
s[i - 1] * power[k] = s[2] * power[2]
即为
(s[1] * base + s[2]) * base ^ 2
分配律一下
s[1] * base ^ 3 + s[2] * base ^ 2
```
两个相减
即为
```
s[3] * base + s[4]
```
那么我们目标不就是这个会等于 $B$ 串吗
很简单易懂吧
## 代码：
# CODE
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#define ull unsigned long long
const int N = 1e6 + 7;
const ull base = 233;
using namespace std;
ull ha[N], power[N];
char s[N];
int len;
inline bool check(ull x, int l) {
for (int i = 1; i <= len; i += l) {
if (x != ha[i + l - 1] - ha[i - 1] * power[l])
return 0;
}
return 1;
}
int main() {
power[0] = 1;
for (int i = 1; i <= N - 7; i ++)
power[i] = power[i - 1] * base;
while (1) {
scanf("%s", s +1);
if (s[1] == '.')
return 0;
len = strlen(s + 1);
ha[0] = 0;
for (int i = 1; i <= len; i ++)
ha[i] = ha[i - 1] * base + (ull)(s[i]);
for (int i = 1; i <= len; i ++) {
if (len % i)
continue;
if (check(ha[i], i)) {
cout << len / i << endl;
break;
}
}
}
}
```
$Good$ $night