奥赛一本通 1461 Beads

1461 Beads

题目大意

给定一个长度为 $n$ 的串，从左往右依次分割为长度均为 $k$ 的子串，最右侧长度小于 $k$ 的部分舍弃，$k$ 为多少时才能使分割出的不同的子串种类数最多（子串可以左右反转）。

知识要点

哈希

解题思路

从小到大枚举 $k$，计算分割出每个子串的在两个方向上的哈希值，去重后即可求出不同的子串数量。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 200005, M = 1e9 + 7;
int s[N], ha1[N], ha2[N], pw[N];
int main() {
int n, cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &s[i]);

pw[0] = 1;
for(int i = 1; i <= n; i++) pw[i] = pw[i – 1] * M;
for(int i = 1; i <= n; i++) ha1[i] = ha1[i – 1] * M + s[i];
for(int i = n; i >= 1; i—) ha2[i] = ha2[i + 1] * M + s[i];

vector<int> ans;
for(int k = 1; k * cnt <= n; k++) { //分割数量小于目前答案时结束
set<long long> S;
for(int i = 1; i + k <= n + 1; i += k) {
int h1 = ha1[i + k – 1] – ha1[i – 1] * pw[k];
int h2 = ha2[i] – ha2[i + k] * pw[k];
S.insert(1ll * h1 * h2); //将两个哈希值的积作为最终的哈希值
}

if(cnt < S.size()) cnt = S.size(), ans.clear();
if(cnt == S.size()) ans.push_back(k);
}

printf("%d %d\\n", cnt, ans.size());
for(int k: ans) printf("%d ", k);
return 0;
}