| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 102782 | Minnakhmetov | 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 <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)
const int N = 3e5 + 5, L = 20, X[2] = { 997, 883 }, M[2] = { 1e9 + 7, 1e9 + 9 };
int suf[L][N], cl[L][N], ct[N], pos[N], lcp[N], lb[N], rb[N];
ll h[2][N], rh[2][N], p[2][N];
int n;
bool isPalindrome(int l, int r) {
for (int i = 0; i < 2; i++) {
ll h1 = (h[i][r + 1] - h[i][l] * p[i][r - l + 1] % M[i] + M[i]) % M[i],
h2 = (rh[i][n - l] - rh[i][n - r - 1] * p[i][r - l + 1] % M[i] + M[i]) % M[i];
if (h1 != h2)
return false;
}
return true;
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
s.push_back('#');
n = s.size();
for (int i = 0; i < n; i++) {
ct[s[i]]++;
cl[0][i] = s[i];
}
for (int i = 1; i < N; i++)
ct[i] += ct[i - 1];
for (int i = n - 1; i >= 0; i--) {
suf[0][--ct[s[i]]] = i;
}
for (int i = 1; i < L; i++) {
fill(ct, ct + N, 0);
for (int j = 0; j < n; j++) {
suf[i - 1][j] -= (1 << (i - 1)) % n;
if (suf[i - 1][j] < 0)
suf[i - 1][j] += n;
ct[cl[i - 1][suf[i - 1][j]]]++;
}
for (int i = 1; i < N; i++) {
ct[i] += ct[i - 1];
}
for (int j = n - 1; j >= 0; j--) {
suf[i][--ct[cl[i - 1][suf[i - 1][j]]]] = suf[i - 1][j];
}
for (int j = 0, k = 0; j < n; j++) {
cl[i][suf[i][j]] = k;
if (cl[i - 1][suf[i][j]] != cl[i - 1][suf[i][j + 1]] ||
cl[i - 1][(suf[i][j] + (1 << (i - 1))) % n] !=
cl[i - 1][(suf[i][j + 1] + (1 << (i - 1))) % n])
k++;
}
}
for (int i = 0; i < n; i++) {
pos[suf[L - 1][i]] = i;
}
for (int i = 0, k = 0; i < n; i++) {
int j = pos[i];
if (j == n - 1) {
k = 0;
continue;
}
j = suf[L - 1][j + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k])
k++;
lcp[pos[i]] = k;
k = max(0, k - 1);
}
n--;
for (int j = 0; j < 2; j++) {
p[j][0] = 1;
for (int i = 0; i < n; i++) {
p[j][i + 1] = p[j][i] * X[j] % M[j];
h[j][i + 1] = (h[j][i] * X[j] + s[i]) % M[j];
rh[j][i + 1] = (rh[j][i] * X[j] + s[n - 1 - i]) % M[j];
}
}
vector<vector<int>> ev;
ll ans = 0;
for (int i = 0; i < n; i++) {
int l = 0, r = min(i + 1, n - i);
while (r - l > 1) {
int p = (l + r) >> 1;
if (isPalindrome(i - p, i + p))
l = p;
else
r = p;
}
ans = max(ans, l * 2 + 1ll);
ev.push_back({ i - l, i, 0 });
if (s[i] == s[i + 1]) {
l = 0, r = min(i + 1, n - i - 1);
while (r - l > 1) {
int p = (l + r) >> 1;
if (isPalindrome(i - p, i + p + 1))
l = p;
else
r = p;
}
ans = max(ans, l * 2 + 2ll);
ev.push_back({ i - l, i, 1 });
}
}
sort(all(ev));
vector<int> v;
for (int i = 1; i <= n; i++) {
while (!v.empty() && lcp[v.back()] >= lcp[i])
v.pop_back();
lb[i] = v.empty() ? 1 : v.back() + 1;
v.push_back(i);
}
v.clear();
for (int i = n; i > 0; i--) {
while (!v.empty() && lcp[v.back()] >= lcp[i])
v.pop_back();
rb[i] = v.empty() ? n - 1 : v.back();
v.push_back(i);
}
set<int> st[2];
for (int i = 0, j = 0; i < n; i++) {
while (j < ev.size() && ev[j][0] == i) {
st[ev[j][2]].insert(ev[j][1]);
j++;
}
int k = pos[i];
if (lcp[k] != 0) {
int r = i + lcp[k] - 1;
auto it = st[0].upper_bound((r - i) / 2 + i);
if (it != st[0].begin()) {
it--;
ll len = (*it - i) * 2 + 1;
ans = max(ans, (rb[k] - lb[k] + 1) * len);
}
it = st[1].upper_bound((r - i - 1) / 2 + i);
if (it != st[1].begin()) {
it--;
ll len = (*it - i) * 2 + 2;
ans = max(ans, (rb[k] - lb[k] + 1) * len);
}
}
}
cout << ans;
return 0;
}