#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; i++)
#define f0r(i, a) f1r(i, 0, a)
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
template <class T> struct SparseTable {
std::vector<T> v;
std::vector<std::vector<int>> jump;
int level(int x) {
return 31 - __builtin_clz(x);
}
int comb(int a, int b) {
return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
}
void init(const std::vector<T>& _v) {
v = _v;
jump = {std::vector<int>((int) v.size())};
iota(jump[0].begin(), jump[0].end(), 0);
for (int j = 1; (1 << j) <= (int) v.size(); j++) {
jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1));
for (int i = 0; i < (int) jump[j].size(); i++)
jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
}
}
int index(int l, int r) {
assert(l <= r);
int d = level(r - l + 1);
return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
}
T query(int l, int r) {
return v[index(l, r)];
}
};
struct SuffixArray {
int n;
std::vector<int> sa, isa, lcp;
std::string s;
SparseTable<int> S;
void init(std::string s_) {
n = (int) (s = s_).size() + 1;
gen_suffix_array();
gen_lcp_array();
}
void gen_suffix_array() {
sa = isa = std::vector<int>(n);
sa[0] = n - 1;
iota(1 + sa.begin(), sa.end(), 0);
sort(1 + sa.begin(), sa.end(), [&](int a, int b) {
return s[a] < s[b]; });
for (int i = 1; i < n; i++) {
int a = sa[i - 1], b = sa[i];
isa[b] = i > 1 && s[a] == s[b] ? isa[a] : i;
}
for (int len = 1; len < n; len *= 2) {
std::vector<int> ss(sa), is(isa), pos(n);
iota(pos.begin(), pos.end(), 0);
for (auto& t : ss) {
int tt = t - len;
if (tt >= 0)
sa[pos[isa[tt]]++] = tt;
}
for (int i = 1; i < n; i++) {
int a = sa[i - 1], b = sa[i];
isa[b] = is[a] == is[b] && is[a + len] == is[b + len] ? isa[a] : i;
}
}
sa.erase(sa.begin());
}
void gen_lcp_array() {
lcp = std::vector<int>(n - 1);
int h = 0;
for (int b = 0; b < n - 1; b++) {
int a = sa[isa[b]];
while (a + h < (int) s.size() && s[a + h] == s[b + h])
h++;
lcp[isa[b] - 1] = h;
if (h)
h--;
}
S.init(lcp);
}
int get_lcp(int a, int b) {
if (a == b)
return (int) s.size() - a;
int l = isa[a], r = isa[b];
if (l > r)
std::swap(l, r);
return S.query(l, r - 1);
}
};
std::vector<int> manacher(std::string s) {
std::string t = "@";
for (auto& c : s)
t += c, t += '#';
t.back() = '&';
std::vector<int> res((int) t.size() - 1);
int lo = 0, hi = 0;
for (int i = 1; i < (int) t.size() - 1; i++) {
if (i != 1)
res[i] = std::min(hi - i, res[hi - i + lo]);
while (t[i - res[i] - 1] == t[i + res[i] + 1])
res[i]++;
if (i + res[i] > hi)
lo = i - res[i], hi = i + res[i];
}
res.erase(res.begin());
for (int i = 0; i < (int) res.size(); i++)
if ((i & 1) == (res[i] & 1))
res[i]++;
return res;
}
ll solve(vi v) {
int n = sz(v);
SparseTable<int> S; S.init(v);
ll ret = 0;
f0r(i, n) {
int l, r;
{
int lo = 0;
int hi = i;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (S.query(mid, i) == v[i]) hi = mid;
else lo = mid + 1;
}
if (S.query(lo, i) == v[i]) l = lo;
else l = hi;
}
{
int lo = i;
int hi = n-1;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (S.query(i, mid) == v[i]) lo = mid;
else hi = mid - 1;
}
if (S.query(i, hi) == v[i]) r = hi;
else r = lo;
}
ret = max(ret, 1LL * (r - l + 2) * v[i]);
}
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
string s; cin >> s;
int n = sz(s);
SuffixArray S; S.init(s);
vi m = manacher(s);
ll ans = 0;
// take care of palindromes that occur exactly once
// We'll consider PAL the 'extension'
for (ll x : m) ans = max(ans, x);
{
// handle even palindromes
// even length palindrome
// say loc i, len L
// consider a contiguous array in suffix array
// [l, r]
// Say they have lcp of x
// min(x, min(PAL [l, r])) * 2 * (r - l + 1)
// each thing has in common at most x
// and each loc has palinndrome size at most PAL
// replace with inner splices, set to min(lcp, PAL[i, i+1]) * 2
// maximize min(l, r) * (r - l + 1) is the new problem?
// check the min gap
// and bash
// okay that works
vi pal(n);
f0r(i, n) {
if (i) pal[i] = m[i*2-1]/2;
}
vi use(n-1);
f0r(i, n-1) {
int i1 = S.sa[i];
int i2 = S.sa[i+1];
int val = min(pal[i1], pal[i2]);
val = min(S.get_lcp(i, i+1), val);
val *= 2;
use[i] = val;
}
ans = max(ans, solve(use));
}
{
// handle odd palindromes
// consider a contiguous array in suffix array
// [l, r]
// say they have lcp of x
// We're considering all of these as the center piece
// (min(x - 1, min(PAL [l, r])) * 2 + 1) * (r - l + 1)
// replace with inner splices, set to min(lcp - 1, PAL[i, i+1]) * 2 + 1
// maximize min(l, r) * (r - l + 1)
// same sub problem
vi pal(n);
f0r(i, n) {
pal[i] = m[2*i] / 2;
}
vi use(n-1);
f0r(i, n-1) {
int i1 = S.sa[i];
int i2 = S.sa[i+1];
int val = min(pal[i1], pal[i2]);
val = min(val, S.get_lcp(i, i+1)-1);
val = 2*val+1;
use[i] = val;
}
ans = max(ans, solve(use));
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
17076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
337 ms |
53780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
