#include <bits/stdc++.h>
#define int long long
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 300 * 1000 + 1 + 23, D = 1000 * 1000 * 1000 + 123, B = 29;
string s;
int n, chi, o[MAXN], val[MAXN], tmp[MAXN], h[MAXN], tav[MAXN], tool[MAXN], ans;
int get(int l, int r) {
return (h[r] - h[l] * tav[r - l] % D) % D;
}
bool cl(pii x, pii y) {
int l = 0, r = min(x.sd - x.ft, y.sd - y.ft) + 1;
while (r - l > 1) {
int mid = ((r + l) >> 1);
if (get(x.ft, x.ft + mid) == get(y.ft, y.ft + mid)) l = mid;
else r = mid;
}
if (l == min(x.sd - x.ft, y.sd - y.ft)) return (x.sd - x.ft) < (y.sd - y.ft);
return s[x.ft + r] < s[y.ft + r];
}
bool clp(pii x, pii y) {
int l = 0, r = min(x.sd - x.ft, y.sd - y.ft) + 1;
while (r - l > 1) {
int mid = ((r + l) >> 1);
if (get(x.ft, x.ft + mid) == get(y.ft, y.ft + mid)) l = mid;
else r = mid;
}
if (l == y.sd - y.ft) return true;
return false;
}
int cnt(int l, int r) {
int dw = -1, up = n;
while (up - dw > 1) {
int mid = ((up + dw) >> 1);
if (cl({o[mid], n}, {l, r})) dw = mid;
else up = mid;
}
int st = up;
dw = st;
up = n;
while (up - dw > 1) {
int mid = ((up + dw) >> 1);
if (clp({o[mid], n}, {l, r})) dw = mid;
else up = mid;
}
// cout << "asdasd" << up << ' ' << st << endl; // deb
return up - st;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
//inp
cin >> s;
n = s.size();
//hs
tav[0] = 1;
for (int i = 1; i < MAXN; i++) tav[i] = tav[i - 1] * B % D;
for (int i = 0; i < n; i++) h[i + 1] = (h[i] * B % D + (s[i] - 'a' + 1)) % D;
//sa
auto cmp = [](int i, int j) {
if (val[i] != val[j]) return val[i] < val[j];
i += chi;
j += chi;
return ((i < n && j < n)? val[i] < val[j]: i > j);
};
for (int i = 0; i < n; i++) {
o[i] = i;
val[i] = s[i];
}
for (chi = 1; tmp[n - 1] != n - 1; chi <<= 1) {
sort(o, o + n, cmp);//Op
for (int i = 0; i < n - 1; i++) tmp[i + 1] = tmp[i] + cmp(o[i], o[i + 1]);
for (int i = 0; i < n; i++) val[o[i]] = tmp[i];
}
//zoj
tool[0] = 0;
tool[1] = ((s[0] == s[1])? 1: 0);
if (tool[1]) ans = max(ans, cnt(0, 2));
for (int i = 2; i < n; i++) {
tool[i] = max(0ll, min(tool[i - 2], tool[i - 1] - 1));
if (tool[i] >= tool[i - 1] - 1) while (i + tool[i] < n && i - tool[i] - 1 >= 0 && s[i + tool[i]] == s[i - tool[i] - 1]) {
tool[i]++;
ans = max(ans, cnt(i - tool[i], i + tool[i]) * (tool[i] << 1));
}
}
//fard
tool[0] = 0;
ans = max(ans, cnt(0, 1));
// cout << "1 " << ans << endl; // deb
tool[1] = ((s[0] == s[2])? 1: 0);
ans = max(ans, cnt(1 - tool[1], 1 + tool[1] + 1));
// cout << "2 " << ans << endl; // deb
for (int i = 2; i < n; i++) {
tool[i] = max(0ll, min(tool[i - 2], tool[i - 1] - 1));
if (tool[i] >= tool[i - 1] - 1) while (i + tool[i] + 1 < n && i - tool[i] - 1 >= 0 && s[i + tool[i] + 1] == s[i - tool[i] - 1]) {
tool[i]++;
ans = max(ans, cnt(i - tool[i], i + tool[i] + 1) * ((tool[i] << 1) | 1));
// cout << "\\ " << s.substr(i - tool[i], ((tool[i] << 1) | 1)) << ' ' << cnt(i - tool[i], i + tool[i] + 1) << ' ' << ((tool[i] << 1) | 1) << endl; // deb
}
}
//out
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
625 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
15092 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
