이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
using namespace std;
const int N = (int) 3e5 + 10;
const int M = (int) 2e6 + 10;
const ll LINF = (ll) 1e18;
const int INF = (int) 1e9 + 7;
const double EPS = (double) 1e-9;
string st;
ll ans;
int lcp[N];
int h[N], h1[N];
int p[N];
int get_hash(int l, int r) {
int ans = (h[r] - (l ? h[l - 1] : 0) + INF) % INF;
ans = ans * 1ll * p[sz(st) - 1 - r] % INF;
return ans;
}
int get_revhash(int l, int r) {
int ans = (h1[l] - h1[r + 1] + INF) % INF;
ans = ans * 1ll * p[l] % INF;
return ans;
}
int first_diff(pii x, pii y) {
int l = 0, r = min(x.s - x.f, y.s - y.f);
int neq = -1;
while (l <= r) {
int m = (l + r) / 2;
if (get_hash(x.f, x.f + m) == get_hash(y.f, y.f + m)) {
l = m + 1;
} else {
neq = m;
r = m - 1;
}
}
return neq;
}
bool cmp(pii x, pii y) {
int neq = first_diff(x, y);
if (neq == -1)
return x.s - x.f < y.s - y.f;
return st[x.f + neq] < st[y.f + neq];
}
void solve_odd() {
vector<pii> v;
for (int i = 0; i < sz(st); i++) {
int l = 0, r = sz(st);
int j = 0;
while (l <= r) {
int m = (l + r) / 2;
if (i - m >= 0 && i + m < sz(st) && get_hash(i, i + m) == get_revhash(i - m, i)) {
l = m + 1;
j = m;
} else {
r = m - 1;
}
}
v.pb(mp(i, i + j));
}
sort(all(v), cmp);
//for (auto it : v) cout << it << endl; cout << "-----\n";
for (int i = 0; i + 1 < sz(v); i++) {
lcp[i] = first_diff(v[i], v[i + 1]);
if (lcp[i] == -1)
lcp[i] = min(v[i].s - v[i].f, v[i + 1].s - v[i + 1].f) + 1;
}
for (int i = 0; i < sz(v); i++) {
int mn = lcp[i];
ans = max(ans, 2ll * (v[i].s - v[i].f + 1) - 1);
for (int j = i; j + 1 < sz(v); j++) {
mn = min(mn, lcp[j]);
ans = max(ans, (j - i + 2) * 1ll * (mn * 2 - 1));
}
}
}
void solve_even() {
vector<pii> v;
for (int i = 0; i < sz(st); i++) {
int l = 0, r = sz(st);
int j = -1;
while (l <= r) {
int m = (l + r) / 2;
if (i - 1 - m >= 0 && i + m < sz(st) && get_hash(i, i + m) == get_revhash(i - 1 - m, i - 1)) {
l = m + 1;
j = m;
} else {
r = m - 1;
}
}
if (j != -1) v.pb(mp(i, i + j));
}
sort(all(v), cmp);
//for (auto it : v) cout << it << endl; cout << "-----\n";
for (int i = 0; i + 1 < sz(v); i++) {
lcp[i] = first_diff(v[i], v[i + 1]);
if (lcp[i] == -1)
lcp[i] = min(v[i].s - v[i].f, v[i + 1].s - v[i + 1].f) + 1;
}
for (int i = 0; i < sz(v); i++) {
int mn = lcp[i];
ans = max(ans, 2ll * (v[i].s - v[i].f + 1));
for (int j = i; j + 1 < sz(v); j++) {
mn = min(mn, lcp[j]);
ans = max(ans, (j - i + 2) * 2ll * mn);
}
}
}
int main() {
#define fn "balls"
#ifdef witch
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen(fn".in", "r", stdin);
// freopen(fn".out", "w", stdout);
#endif
cin >> st;
p[0] = 1;
for (int i = 1; i < sz(st); i++) {
p[i] = p[i - 1] * 37LL % INF;
}
for (int i = 0; i < sz(st); i++) {
if (i) {
h[i] = h[i - 1];
}
h[i] = (h[i] + (st[i] - 'a' + 1) * 1LL * p[i]) % INF;
}
for (int i = sz(st) - 1; i >= 0; i--) {
h1[i] = (h1[i + 1] + (st[i] - 'a' + 1) * 1ll * p[sz(st) - 1 - i]) % INF;
}
solve_odd();
solve_even();
cout << ans;
return 0;
}
# | 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... |