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 <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2", "popcnt")
using namespace std;
const int MAXN = 3e5 + 10;
inline vector<int> build_sa(string s){
int n = s.size();
vector<int> a(n);
vector<int> eq(2 * n + 1);
vector<int> nw(2 * n + 1);
vector<int> t(n + 2);
vector<int> nw_a(n);
for (int i = 0; i < n; i++){
a[i] = i;
}
sort(a.begin(), a.end(), [&](int x, int y){
if (s[x] != s[y]){
return s[x] < s[y];
}
return x < y;
});
eq[a[0]] = 0;
for (int i = 1; i < n; i++){
eq[a[i]] = eq[a[i - 1]];
if (s[a[i]] != s[a[i - 1]]){
eq[a[i]]++;
}
}
for (int k = 0; (1 << k) < n; k++){
for (int f = 1; f >= 1; f--){
t.assign(n + 2, 0);
for (int i = 0; i < n; i++){
int j = (a[i] - (f << k) + n) % n;
// if (eq[j] + 1 < t.size()){
t[eq[j]]++;
// }
}
for (int i = 1; i <= n; i++){
t[i] += t[i - 1];
}
// for (int i = n; i >= 1; i--){
// t[i] = t[i - 1];
// }
for (int i = n - 1; i >= 0; i--){
int j = (a[i] - (f << k) + n) % n;
nw_a[--t[eq[j]]] = a[i];
}
nw_a.swap(a);
}
nw[a[0]] = 1;
for (int i = 1; i < n; i++){
int p = a[i];
int q = a[i - 1];
nw[p] = nw[q];
if (eq[p] != eq[q] || eq[p + (1 << k)] != eq[q + (1 << k)]){
nw[p]++;
}
}
nw.swap(eq);
}
a.insert(a.begin(), n);
return a;
}
inline vector<int> build_lcp(const vector<int>& p, const string& s){
int n = s.size();
vector<int> pos(n + 1);
for (int i = 0; i <= n; i++){
pos[p[i]] = i;
}
vector<int> lcp(n);
int k = 0;
for (int i = 0; i < (n - 1); i++){
while (s[i + k] == s[p[pos[i] - 1] + k]){
k++;
}
lcp[pos[i] - 1] = k;
k -= (k != 0);
}
return lcp;
}
struct SparseTable{
vector<vector<int>> st;
SparseTable(vector<int> a){
int n = a.size();
st.resize(n);
for (int i = 0; i < n; i++){
st[i].push_back(a[i]);
}
for (int k = 1; k <= n; k *= 2){
for (int i = 0; i + k < n; i++){
st[i].push_back(min(st[i].back(), st[i + k].back()));
}
}
}
inline int log2(int x){
return 31 - __builtin_clz(x);
}
inline int get(int l, int r){
if (l > r){
return 1e9;
}
int k = log2(r - l + 1);
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
};
SparseTable sp({});
vector<int> d(MAXN);
vector<int> pos;
string s;
inline int lcp(int i, int j){
int l = pos[i];
int r = pos[j];
if (l > r){
swap(l, r);
}
return min({d[i], d[j], sp.get(l, r - 1)});
}
inline int cmp(int i, int j){
int l = lcp(i, j);
if (l == min(d[i], d[j])){
return d[i] < d[j];
}
return s[i - l] < s[j - l];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef ON_PC
freopen("input.txt", "r", stdin);
#endif
// freopen("output.txt", "w", stdout);
int T = 1;
// cin >> T;
while (T--){
cin >> s;
int n = s.size();
vector<int> sa = build_sa(s);
vector<int> lcpv = build_lcp(sa, s);
pos = vector<int>(n + 2);
for (int i = 0; i < sa.size(); i++){
pos[sa[i] + 1] = i;
}
sp = SparseTable(lcpv);
s = " " + s;
ll res = 0;
vector<int> order(n);
vector<int> lb(n);
vector<int> rb(n);
vector<int> st;
vector<int> lcp_res(n);
for (int f = 0; f < 2; f++){
d.assign(n + 1, 0);
for (int i = 1, l = 0, r = -1; i <= n; i++){
if (i + f <= r){
d[i] = min(r - (i + f) + 1, d[l + r - (i + f)]);
}
while (i - d[i] >= 1 && i + f + d[i] <= n &&
s[i - d[i]] == s[i + f + d[i]]){
d[i]++;
}
if (i + f + d[i] - 1 > r){
r = i + f + d[i] - 1;
l = i - d[i] + 1;
}
}
for (int i = 1; i <= n; i++){
res = max(res, (ll)(2 * d[i] - !f));
}
for (int i = 1; i <= n; i++){
order[i - 1] = i;
}
sort(all(order), cmp);
for (int i = 0; i + 1 < n; i++){
lcp_res[i] = lcp(order[i], order[i + 1]);
}
for (int i = 0; i < n; i++){
while (!st.empty() && lcp_res[st.back()] >= lcp_res[i]){
st.pop_back();
}
lb[i] = 0;
if (!st.empty()){
lb[i] = st.back() + 1;
}
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--){
while (!st.empty() && lcp_res[st.back()] >= lcp_res[i]){
st.pop_back();
}
rb[i] = n - 1;
if (!st.empty()){
rb[i] = st.back();
}
st.push_back(i);
}
st.clear();
for (int i = 0; i < n; i++){
res = max(res, (2 * lcp_res[i] - !f) * 1ll * (rb[i] - lb[i] + 1));
}
}
cout << res << "\n";
}
return 0;
}
Compilation message (stderr)
palindrome.cpp: In function 'int main()':
palindrome.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for (int i = 0; i < sa.size(); i++){
| ~~^~~~~~~~~~~
# | 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... |