#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
using namespace std;
#define int long long
#define less less228
#define left left228
#define right right228
template<typename T> void uin(T &a, T b) {
if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
if (b > a) a = b;
}
random_device rnd;
template<typename T> void shuffle(vector< T > &v) {
for (int i = 1; i < (int)v.size(); ++i) {
swap(v[rnd() % i], v[i]);
}
for (int i = (int)v.size() - 1; i; --i) {
swap(v[rnd() % i], v[i]);
}
}
const int N = 100 * 1000 + 228;
const int BASE = 141, MOD = 2286661337;
const int INF = 1e9 + 228;
int mod(int x) {
x %= MOD;
if (x < 0) x += MOD;
return x;
}
vector<int> get_suffmas(string s) {
s += '$';
int n = (int)s.size();
vector<int> p(n), c(n), cnt(max(256LL, n));
for (int i = 0; i < n; ++i) {
++cnt[(int)s[i]];
}
for (int i = 1; i < (int)cnt.size(); ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = 0; i < n; ++i) {
p[--cnt[(int)s[i]]] = i;
}
c[p[0]] = 0;
for (int i = 1; i < n; ++i) {
c[p[i]] = c[p[i - 1]];
if (s[p[i]] != s[p[i - 1]]) ++c[p[i]];
}
for (int d = 0; (1 << d) < n; ++d) {
vector<int> pp(n), cc(n);
cnt.assign(n, 0);
for (int i = 0; i < n; ++i) {
pp[i] = p[i] - (1 << d);
if (pp[i] < 0) pp[i] += n;
++cnt[c[pp[i]]];
}
for (int i = 0; i < n; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i + 1; --i) {
p[--cnt[c[pp[i]]]] = pp[i];
}
cc[p[0]] = 0;
for (int i = 1; i < n; ++i) {
cc[p[i]] = cc[p[i - 1]];
if (c[p[i]] != c[p[i - 1]] || c[(p[i] + (1 << d) % n)] != c[(p[i - 1] + (1 << d)) % n]) {
++cc[p[i]];
}
}
c = cc;
}
vector<int> ans;
for (int i : p) {
if (i != n - 1) {
ans.push_back(i);
}
}
return ans;
}
vector<int> get_lcp(string s, vector<int> p) {
int n = (int)s.size();
vector<int> pos(n), lcp(n - 1);
for (int i = 0; i < n; ++i) {
pos[p[i]] = i;
}
int k = 0;
for (int i = 0; i < n; ++i) {
if (k) --k;
if (pos[i] == n - 1) {
k = 0;
} else {
int j = p[pos[i] + 1];
while (max(i, j) + k < n && s[i + k] == s[j + k]) ++k;
lcp[pos[i]] = k;
}
}
return lcp;
}
int n;
string s;
int go_even[N];
int go_odd[N];
int base[N], h[N], hr[N];
int mx[N], lg[N], st_even[N][20], st_odd[N][20];
int get_hash(int l, int r) {
return mod(h[r] - h[l - 1] * base[r - l + 1]);
}
int get_rhash(int l, int r) {
return mod(hr[l] - hr[r + 1] * base[r - l + 1]);
}
void build_sparse() {
for (int i = 2; i <= n; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= n; ++i) {
st_even[i][0] = go_even[i];
st_odd[i][0] = go_odd[i];
}
for (int k = 1; k <= lg[n]; ++k) {
for (int i = 1; i <= n - (1 << k) + 1; ++i) {
st_even[i][k] = min(st_even[i][k - 1], st_even[i + (1 << (k - 1))][k - 1]);
st_odd[i][k] = min(st_odd[i][k - 1], st_odd[i + (1 << (k - 1))][k - 1]);
}
}
}
int get_even(int l, int r)
{
int k = lg[r - l + 1];
return min(st_even[l][k], st_even[r - (1 << k) + 1][k]);
}
int get_odd(int l, int r) {
int k = lg[r - l + 1];
return min(st_odd[l][k], st_odd[r - (1 << k) + 1][k]);
}
int res = 0;
void pre() {
base[0] = 1;
for (int i = 1; i <= n; ++i) {
base[i] = mod(base[i - 1] * BASE);
}
for (int i = 1; i <= n; ++i) {
h[i] = mod(h[i - 1] * BASE + (int)s[i - 1]);
}
for (int i = n; i; --i) {
hr[i] = mod(hr[i + 1] * BASE + (int)s[i - 1]);
}
for (int i = 1; i <= n; ++i) {
int l = 1, r = min(i, n - i + 1) + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (get_hash(i - mid + 1, i + mid - 1) == get_rhash(i - mid + 1, i + mid - 1)) {
l = mid;
} else {
r = mid;
}
}
go_odd[i] = i - l + 1;
uax(res, 2 * l - 1);
}
for (int i = 1; i <= n; ++i) {
int l = 1, r = min(i, n - i) + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (get_hash(i - mid + 1, i + mid) == get_rhash(i - mid + 1, i + mid)) {
l = mid;
} else {
r = mid;
}
}
if (i + l <= n && get_hash(i - l + 1, i + l) == get_rhash(i - l + 1, i + l)) {
go_even[i] = i - l + 1;
uax(res, 2 * l);
} else {
go_even[i] = INF;
}
}
build_sparse();
}
int max_palindrome(int L, int R) {
++L, ++R;
int x = L + (R - L) / 2;
int l = L, r = x + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (get_odd(mid, x) <= L) {
l = mid;
} else {
r = mid;
}
}
int len = 2 * (l - L + 1) - 1;
x = L + (R - L - 1) / 2;
l = L, r = x + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (get_even(mid, x) <= L) {
l = mid;
} else {
r = mid;
}
}
if (L + l <= n && get_even(l, x) <= L) {
uax(len, 2 * (l - L + 1));
} else {
// kekos)))))))))))
}
return len;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> s;
n = (int)s.size();
vector<int> p = get_suffmas(s);
vector<int> lcp = get_lcp(s, p);
pre();
vector<int> gol(n), gor(n);
for (int i = 0; i < n - 1; ++i) {
gol[i] = -1;
gor[i] = n - 1;
}
vector<int> st;
for (int i = 0; i < n - 1; ++i) {
while (!st.empty() && lcp[st.back()] > lcp[i]) {
gor[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
st.clear();
for (int i = n - 2; i + 1; --i) {
while (!st.empty() && lcp[st.back()] > lcp[i]) {
gol[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
for (int i = 0; i < n - 1; ++i) {
if (lcp[i] == 0) continue;
int cnt = gor[i] - gol[i];
int len = max_palindrome(p[i], p[i] + lcp[i] - 1);
uax(res, len * cnt);
}
cout << res << '\n';
return 0;
}
// RU_023
/*
shironury
boootgslkfjdaojfdopsjfopjso
pgjq]pogjopsjg\qrwjopg
j
pogjqwrjgp]oqwjjqw]pjljfojpjowjow4jgopja ohbip]aeo'rogpoaj0
[bkrw
pojgqwjp\\j\;sync_with_stdiojp
ojeofmpworuc[owejgoprwig
[sdkz
pgj
p[gjes
p0ghjqsp[
jg
prsjgopjg]prwjgoprejgopjrepogjrepog]jgoprejgrgjporeqjgoperjgoprejgopeqrjgopeqrjgoprqwjgpoqjrwsopt4ng\ojsbjsoprnbfqsn\bvhqerpogjorwo
pwewh\rwh \wjiowe orw jop jgr\p jpj o jopj gr\pj p gjop j\pj\pe jp'oj [
k
p[eq fj\pjfdwj\ejopjojopjopjf;'djpfsj, ipojs\p gpsdigsj gorkgjgjrogjdojgiao'fsdvopdshpdfidopcnweojccodj [cjd;ofjd[jdspmcojc"ajno[:Afvoq[w0shbprs`nm/jP{Vadmn;'fnc[Ajojsfpfjcffor 9int i= ; 1 < nfor (int i =1; for (int i =1 ; i <= n: ++i) frfor (int j = 1; j <= ml; ++'}]]]]]]]]]
5
1 5
1 2
2 3
2 4
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
3 ms |
760 KB |
Output is correct |
| 4 |
Correct |
3 ms |
760 KB |
Output is correct |
| 5 |
Correct |
3 ms |
764 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
6 ms |
1400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
30 ms |
9108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
40 ms |
25688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
