| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 16190 | erdemkiraz | Palindromes (APIO14_palindrome) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
#define hash ___hash
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;
const int N = 3e5 + 5;
const int LOG = 19;
const int ODD = 0;
const int EVEN = 1;
const int QU = 2;
int n;
char s[N];
class event{ public:
int x, id, type;
bool operator<(event oth) const {
if(x != oth.x)
return x < oth.x;
return type < oth.type;
}
};
int go_odd[N], go_even[N], tmp[N << 1], rad[N << 1];
void manacher()
{
for(int i = 0; i < n * 2 + 1; i++) tmp[i] = '#';
for(int i = 0; i < n; i++) tmp[i * 2 + 1] = s[i + 1];
int i=0,j=0;
int N=n*2+1;
for(int i=0;i<N;)
{
while(i-j>=0&&i+j<N&&tmp[i-j]==tmp[i+j])j++;
rad[i]=j;
int k=1;
while(rad[i-k]<rad[i]-k)rad[i+k]=rad[i-k],k++;
i+=k;
j=max(0,j-k);
}
//for(int i = 0; i < N; i++)
// printf("rad[%d] = %d\n", i, rad[i]);
for(int i = 1; i <= n; i++)
go_odd[i] = rad[(i - 1) * 2 + 1] / 2;
for(int i = 1; i <= n; i++)
go_even[i - 1] = rad[(i - 1) * 2] / 2;
//for(int i = 1; i <= n; i++)
// printf("go_odd[%d] = %d\n", i, go_odd[i]);
//for(int i = 1; i <= n; i++)
// printf("go_even[%d] = %d\n", i, go_even[i]);
}
int suf[N], order[N], lcp_table[N];
pair < ii, int > p[N];
vector < ii > sort_helper[N];
void fast_sort() {
int m = max(n, 'z');
for(int i = 1; i <= n; i++)
sort_helper[p[i].first.second].push_back(ii(p[i].first.first, p[i].second));
int ptr = 0;
for(int i = 0; i <= m; i++) {
for(int j = 0; j < sort_helper[i].size(); j++)
p[++ptr] = {{sort_helper[i][j].first, i}, sort_helper[i][j].second};
sort_helper[i].clear();
}
for(int i = 1; i <= n; i++)
sort_helper[p[i].first.first].push_back(ii(p[i].first.second, p[i].second));
ptr = 0;
for(int i = 0; i <= m; i++) {
for(int j = 0; j < sort_helper[i].size(); j++)
p[++ptr] = {{i, sort_helper[i][j].first}, sort_helper[i][j].second};
sort_helper[i].clear();
}
}
bool one_pass(int k) {
for(int i = 1; i <= n; i++)
p[i] = {{suf[i], i + (1 << k) <= n ? suf[i + (1 << k)] : 0}, i};
fast_sort();
//sort(p + 1, p + n + 1);
int ptr = 1;
for(int i = 1; i <= n; i++) {
if(i - 1 >= 1 and p[i - 1].first != p[i].first)
ptr++;
suf[p[i].second] = ptr;
}
return ptr == n;
}
void build_sa() {
for(int i = 1; i <= n; i++)
suf[i] = s[i];
for(int i = 0; i < LOG; i++)
if(one_pass(i))
break;
for(int i = 1; i <= n; i++)
order[suf[i]] = i;
//for(int i = 1; i <= n; i++)
// printf("order[%d] = %d\n", i, order[i]);
}
void build_lcp() {
int j = 0;
for(int i = 1; i <= n; i++) {
if(suf[i] == 1)
continue;
while(i + j <= n and order[suf[i] - 1] + j <= n and s[i + j] == s[order[suf[i] - 1] + j])
j++;
lcp_table[suf[i]] = j;
if(j)
j--;
}
//for(int i = 1; i <= n; i++)
// printf("lcp_table[%d] = %d\n", i, lcp_table[i]);
}
int a[N];
ll ans;
void build_table() {
vector < event > v;
for(int i = 1; i <= n; i++) {
v.push_back({i - go_odd[i] + 1, i, ODD});
if(go_even[i])
v.push_back({i - go_even[i] + 1, i, EVEN});
v.push_back({i, i, QU});
}
sort(v.begin(), v.end());
set < int > s1, s2;
foreach(it, v) {
int x = it -> id;
int type = it -> type;
//printf("len = %d x = %d type = %d\n", it -> x, x, type);
if(type == ODD)
s1.insert(x);
else if(type == EVEN)
s2.insert(x);
else {
int val1 = (lcp_table[suf[x]] + 2 * x - 1) / 2;
int val2 = (lcp_table[suf[x]] + 2 * x - 2) / 2;
set < int > :: iterator it = s1.upper_bound(val1);
if(it != s1.begin()) {
it--;
a[suf[x]] = max(a[suf[x]], (*it - x) * 2 + 1);
}
if(s2.size()) {
it = s2.upper_bound(val2);
if(it != s2.begin()) {
it--;
a[suf[x]] = max(a[suf[x]], (*it - x) * 2 + 2);
}
}
}
}
//for(int i = 1; i <= n; i++)
// printf("a[%d] = %d\n", i, a[i]);
}
int sz;
ii vec[N];
void solve() {
for(int i = 1; i <= n; i++)
ans = max(ans, (ll) max(go_odd[i] * 2 - 1, go_even[i] * 2));
build_table();
for(int i = 2; i <= n + 1; i++) {
int st = i;
while(sz and vec[sz - 1].first >= a[i]) {
ans = max(ans, (ll) (i - vec[sz - 1].second + 1) * vec[sz - 1].first);
st = vec[sz - 1].second;
sz--;
}
vec[sz++] = ii(a[i], st);
}
}
int main () {
scanf("%s", s + 1);
n = strlen(s + 1);
//n = 3e5;
//for(int i = 1; i <= n; i++)
// s[i] = 'a';
build_sa();
manacher();
build_lcp();
solve();
printf("%lld\n", ans);
//printf("%.12lf\n", (double) clock() / CLOCKS_PER_SEC);
return 0;
}