This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//InTheNameOfGOD
//PRS;)
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; ++i)
#define per(i, l, r) for(int i = r - 1; i >= l; --i)
#define Fast cin.tie(0) -> sync_with_stdio(0);
#define X first
#define Y second
typedef long long ll;
using namespace std;
typedef pair<int, pair<int, int>> pi;
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
constexpr ll mod = 2e9 + 11;
constexpr int xn = 3e5 + 5;
ll h1[xn], h2[xn], p[xn];
int a[xn], t[xn];
char s[xn];
inline ll mk(ll x, ll y, int z)
{
y = (y * p[z]) % mod, x -= y;
return x < 0 ? x + mod : x;
}
inline int lcp(int x, int y)
{
int l = 1, r = min(t[x], t[y]) + 1;
while(l < r)
{
int md = l + r >> 1;
mk(h1[x + md], h1[x], md) == mk(h1[y + md], h1[y], md) ? l = md + 1 : r = md;
}
return l - 1;
}
inline bool cmp(int x, int y)
{
int z = lcp(x, y);
if(t[y] <= z) return 0;
if(t[x] <= z) return 1;
return s[x + z] < s[y + z];
}
int main()
{
Fast
scanf("%s", &s);
int n = strlen(s);
h1[0] = h2[n] = 0, p[0] = 1;
rep(i, 0, n) h1[i + 1] = (h1[i] * 27 + s[i] - 'a' + 1) % mod;
per(i, 0, n) h2[i] = (h2[i + 1] * 27 + s[i] - 'a' + 1) % mod;
rep(i, 1, n + 1) p[i] = (p[i - 1] * 27) % mod;
ll ans = 1;
rep(i, 0, n)
{
int l = 2, r = min(n - i, i + 1) + 1;
while(l < r)
{
int md = l + r >> 1;
mk(h1[i + md], h1[i], md) == mk(h2[i - md + 1], h2[i + 1], md) ? l = md + 1 : r = md;
}
t[i] = l - 1;
ans = max(ans, 1ll * ((t[i] << 1) - 1));
}
rep(i, 0, n) a[i] = i;
sort(a, a + n, cmp);
vector<pi> v;
rep(i, 1, n)
{
int e = lcp(a[i - 1], a[i]), prs = 0;
while(!v.empty() && v.back().X >= e)
{
pi j = v.back();
v.pop_back();
if(j.X > e) ans = max(ans, 1ll * ((j.X << 1) - 1) * (i - j.Y.X));
}
if(!v.empty()) prs = v.back().Y.Y;
v.push_back({e, {prs, i}});
}
rep(i, 0, n)
{
int l = 1, r = min(n - i, i) + 1;
while(l < r)
{
int md = l + r >> 1;
mk(h1[i + md], h1[i], md) == mk(h2[i - md], h2[i], md) ? l = md + 1 : r = md;
}
t[i] = l - 1;
ans = max(ans, 1ll * (t[i] << 1));
}
sort(a, a + n, cmp);
for(pi i : v) ans = max(ans, 1ll * ((i.X << 1) - 1) * (n - i.Y.X));
v.clear();
rep(i, 1, n)
{
int e = lcp(a[i - 1], a[i]), prs = 0;
while(!v.empty() && v.back().X >= e)
{
pi j = v.back();
v.pop_back();
if(j.X > e) ans = max(ans, 1ll * (j.X << 1) * (i - j.Y.X));
}
if(!v.empty()) prs = v.back().Y.Y;
v.push_back({e, {prs, i}});
}
for(pi i : v) ans = max(ans, 1ll * (i.X << 1) * (n - i.Y.X));
printf("%lld\n", ans);
}
Compilation message (stderr)
palindrome.cpp: In function 'int lcp(int, int)':
palindrome.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int md = l + r >> 1;
| ~~^~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:44:10: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
44 | scanf("%s", &s);
| ~^ ~~
| | |
| | char (*)[300005]
| char*
palindrome.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int md = l + r >> 1;
| ~~^~~
palindrome.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int md = l + r >> 1;
| ~~^~~
palindrome.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%s", &s);
| ~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |