很牛逼的题啊!感觉套路很实用,感谢 ntf。
考虑 \(totlen = cnt \times len \le 80\)。若 \(cnt \le 3\),可以 \(O(|S|^{2cnt - 1})\) 暴力枚分割点。\(cnt = 4\) 包含在 \(cnt = 2\) 内,无需考虑。\(cnt \ge 5\) 也即 \(len \le 16\),这时候有一个很牛逼的结论:答案的循环节一定包含于 \(S\) 的其中一个长度为 \(16\) 的子串内。证明考虑反证,若均不包含则 \(cnt\) 不可能取到 \(\ge 5\)。然后暴力枚举循环节即可。
启发:没有好的想法考虑根号分治或类根号分治(此题)。
code
// Problem: F. Serval and Brain Power
// Contest: Codeforces - Codeforces Round 853 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1789/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 85;
int n, m, m1, m2, m3, f[maxn][maxn], g[maxn][maxn][maxn];
char s[maxn], t[maxn], a[maxn], b[maxn], c[maxn];
void solve() {
scanf("%s", s + 1);
n = strlen(s + 1);
int ans = 0;
for (int p = 1; p < n; ++p) {
m1 = m2 = 0;
for (int i = 1; i <= p; ++i) {
a[++m1] = s[i];
}
for (int i = p + 1; i <= n; ++i) {
b[++m2] = s[i];
}
for (int i = 0; i <= m1; ++i) {
for (int j = 0; j <= m2; ++j) {
f[i][j] = 0;
}
}
for (int i = 1; i <= m1; ++i) {
for (int j = 1; j <= m2; ++j) {
f[i][j] = max({f[i - 1][j], f[i][j - 1], a[i] == b[j] ? f[i - 1][j - 1] + 1 : 0});
}
}
ans = max(ans, f[m1][m2] * 2);
}
for (int p1 = 1; p1 < n; ++p1) {
for (int p2 = p1 + 1; p2 < n; ++p2) {
m1 = m2 = m3 = 0;
for (int i = 1; i <= p1; ++i) {
a[++m1] = s[i];
}
for (int i = p1 + 1; i <= p2; ++i) {
b[++m2] = s[i];
}
for (int i = p2 + 1; i <= n; ++i) {
c[++m3] = s[i];
}
for (int i = 0; i <= m1; ++i) {
for (int j = 0; j <= m2; ++j) {
for (int k = 0; k <= m3; ++k) {
g[i][j][k] = 0;
}
}
}
for (int i = 1; i <= m1; ++i) {
for (int j = 1; j <= m2; ++j) {
for (int k = 1; k <= m3; ++k) {
g[i][j][k] = max({g[i - 1][j][k], g[i][j - 1][k], g[i][j][k - 1], (a[i] == b[j] && b[j] == c[k]) ? g[i - 1][j - 1][k - 1] + 1 : 0});
}
}
}
ans = max(ans, g[m1][m2][m3] * 3);
}
}
for (int i = 1; i <= n; ++i) {
for (int S = 1; S < (1 << 16); ++S) {
m = 0;
for (int j = 0; j < 16 && i + j <= n; ++j) {
if (S & (1 << j)) {
t[++m] = s[i + j];
}
}
int cnt = 0;
for (int j = 1, k = 1; j <= n; ++j) {
if (s[j] == t[k]) {
if ((++k) > m) {
k = 1;
++cnt;
}
}
}
ans = max(ans, cnt > 1 ? cnt * m : 0);
}
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}