이 제출은 이전 버전의 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;
int ini;
string s;
const int N = 6e5 + 5;
int a[N];
int cl[N];
int lcp[N];
int par[N];
int len[N];
int val[N];
bool cmp(int x, int y) {
if (lcp[x] < lcp[y]) {
return false;
}
if (lcp[x] > lcp[y]) {
return true;
}
bool diffa = (a[x - 1] < ini) ^ (a[x] < ini);
bool diffb = (a[y - 1] < ini) ^ (a[y] < ini);
return diffa < diffb;
}
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 init() {
}
void input() {
cin >> s;
n = sz(s);
ini = n;
string t = s;
reverse(t.begin(), t.end());
s = s + '$' + t + '\0';
n = sz(s);
}
void solve() {
cresuff();
crelcp();
for (int i = 0; i < n; i++) {
par[i] = i;
len[i] = 1;
val[i] = (a[i] < ini);
// cout << i << ' ' << s.substr(a[i]) << ' ' << lcp[i] << ' ' << val[i] << endl;
}
vector<int> edges;
for (int i = 1; i < n; i++) {
edges.pb(i);
}
sort(edges.begin(), edges.end(), cmp);
ll ans = 0;
for (int i = 0; i < n - 1; i++) {
int ind = edges[i];
int p1 = par[ind - 1];
int p2 = par[ind];
// cout << ind << ' ' << lcp[ind] << ' ' << (a[ind - 1]) << ' ' << (a[ind]) << endl;
if (lcp[ind]) {
if ((a[ind - 1] < ini) ^ (a[ind] < ini)) {
int i1 = a[ind - 1];
int i2 = a[ind];
if (i1 >= ini) {
i1 = 2 * ini - i1;
}
if (i2 >= ini) {
i2 = 2 * ini - i2;
}
int dist = abs(i1 - i2) + 1;
// cout << " " << i1 << ' ' << i2 << ' ' << val[p1] << ' ' << val[p2] << ' ' << min(dist, lcp[ind]) * (val[p1] + val[p2]) << endl;
if (lcp[ind] >= dist) {
ans = max(ans, 1ll * min(dist, lcp[ind]) * (val[p1] + val[p2]));
}
}
}
if (len[p1] < len[p2]) {
for (int i = ind - len[p1]; i < ind; i++) {
par[i] = p2;
}
len[p2] += len[p1];
val[p2] += val[p1];
}
else {
for (int i = ind; i < ind + len[p2]; i++) {
par[i] = p1;
}
len[p1] += len[p2];
val[p1] += val[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... |