이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int p = 2;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;
int n;
string s;
const int N = 3e5 + 5;
int hashed[N];
int hsahed[N];
int po[N];
int a[N];
int cl[N];
int lcp[N];
int par[N];
int len[N];
int mull(int a, int b) {
return (1ll * a * b) % mod;
}
void cntsort() {
vector<int> have[n];
for (int i = 0; i < n; i++) {
have[cl[a[i]]].pb(a[i]);
}
int ind = 0;
for (int i = 0; i < n; i++) {
for (auto x : have[i]) {
a[ind] = x;
ind++;
}
}
}
void cresuff() {
pair<char, int> arr[n];
for (int i = 0; i < n; i++) {
arr[i] = mp(s[i], i);
}
sort(arr + 0, arr + n);
a[0] = arr[0].se;
cl[a[0]] = 0;
for (int i = 1; i < n; i++) {
a[i] = arr[i].se;
if (arr[i].fi == arr[i - 1].fi) {
cl[a[i]] = cl[a[i - 1]];
}
else {
cl[a[i]] = cl[a[i - 1]] + 1;
}
}
int len = 1;
while (len < n) {
for (int i = 0; i < n; i++) {
a[i] -= len;
a[i] += n;
a[i] %= n;
}
cntsort();
int cl2[n];
cl2[a[0]] = 0;
for (int i = 1; i < n; i++) {
pair<int, int> pre = mp(cl[a[i - 1]], cl[(a[i - 1] + len) % n]);
pair<int, int> now = mp(cl[a[i]], cl[(a[i] + len) % n]);
if (pre == now) {
cl2[a[i]] = cl2[a[i - 1]];
}
else {
cl2[a[i]] = cl2[a[i - 1]] + 1;
}
}
for (int i = 0; i < n; i++) {
cl[i] = cl2[i];
}
len <<= 1;
}
}
void crelcp() {
int have = 0;
for (int i = 0; i < n - 1; i++) {
int ind = cl[i];
while (i + have < n && a[ind - 1] + have < n) {
if (s[i + have] != s[a[ind - 1] + have]) {
break;
}
have++;
}
lcp[ind] = have;
have = max(0, have - 1);
}
}
void crehash() {
po[0] = 1;
for (int i = 1; i <= n; i++) {
po[i] = mull(po[i - 1], p);
}
hashed[0] = (int)s[0];
for (int i = 1; i < n; i++) {
hashed[i] = mull(hashed[i - 1], p);
hashed[i] += (int)s[i];
}
hsahed[n - 1] = (int)s[n - 1];
for (int i = n - 2; i >= 0; i--) {
hsahed[i] = mull(hsahed[i + 1], p);
hsahed[i] += (int)s[i];
}
}
bool palin(int l, int r) {
int val;
if (l == 0) {
val = hashed[r];
}
else {
val = hashed[r] - mull(po[r - l + 1], hashed[l - 1]);
val += mod;
val %= mod;
}
int lav;
if (r == n - 1) {
lav = hsahed[l];
}
else {
lav = hsahed[l] - mull(po[r - l + 1], hsahed[r + 1]);
lav += mod;
lav %= mod;
}
bool ok = true;
for (int i = 0; l + i < r - i; i++) {
if (s[l + i] != s[r - i]) {
ok = false;
}
}
if (ok != (val == lav)) {
throw;
}
return ok;
}
void init() {
}
void input() {
cin >> s;
n = sz(s);
n++;
s += '$';
}
void solve() {
cresuff();
crelcp();
crehash();
for (int i = 0; i < n; i++) {
par[i] = i;
len[i] = 1;
}
vector<pair<int, int>> edges;
for (int i = 1; i < n; i++) {
edges.pb(mp(lcp[i], i));
}
sort(edges.begin(), edges.end());
reverse(edges.begin(), edges.end());
ll ans = 0;
if (palin(0, n - 2)) {
ans = n - 1;
}
for (int i = 0; i < n - 1; i++) {
int ind = edges[i].se;
int p1 = par[ind - 1];
int p2 = par[ind];
if (palin(a[ind], a[ind] + lcp[ind] - 1)) {
ans = max(ans, 1ll * lcp[ind] * (len[p1] + len[p2]));
}
if (len[p1] < len[p2]) {
for (int i = ind - len[p1]; i < ind; i++) {
par[i] = p2;
}
len[p2] += len[p1];
}
else {
for (int i = ind; i < ind + len[p2]; i++) {
par[i] = p1;
}
len[p1] += len[p2];
}
}
cout << ans;
}
void output() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int number_of_testcases = 1;
//cin >> number_of_testcases;
while (number_of_testcases--) {
init();
input();
solve();
output();
}
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... |