이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 300010
using namespace std;
int n;
string s;
int d1[MAXN];
int d2[MAXN];
int sa[MAXN];
// used for suffix array
int classes[MAXN];
int old_sa[MAXN];
int old_c[MAXN];
int idx[MAXN];
int cnt[MAXN];
// used for lcp
int inv_sa[MAXN];
int lcp[MAXN];
ll ans;
struct DSU {
int dsu[MAXN];
int sz[MAXN];
void reset() {
iota(dsu, dsu + n, 0);
fill(sz, sz + n, 1);
}
int find(int x) {
return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
}
void join(int x, int y) {
if (((x = find(x)) != (y = find(y)))) {
if (sz[x] < sz[y]) swap(x, y);
dsu[y] = x;
sz[x] += sz[y];
}
}
} dsu;
void manachers() {
// odd length palindrome
int l = 0;
int r = -1;
for (int i = 0; i < n; i++) {
int k = 1;
if (i <= r) k = min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
// even length palindrome
l = 0;
r = -1;
for (int i = 0; i < n; i++) {
int k = 0;
if (i <= r) k= min(d1[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++;
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
}
}
void suffix_array() {
for (int i = 0; i < n; i++) {
sa[i] = n - i - 1;
classes[i] = s[i];
}
stable_sort(sa, sa + n, [](int i, int j) { return s[i] < s[j]; });
for (int len = 1; len < n; len *= 2) {
copy(sa, sa + n, old_sa);
copy(classes, classes + n, old_c);
fill(idx, idx + n, 1);
iota(cnt, cnt + n, 0);
for (int i = 0; i < n; i++) {
bool same = i && sa[i - 1] + len < n
&& old_c[sa[i]] == old_c[sa[i - 1]]
&& old_c[sa[i] + len / 2] == old_c[sa[i - 1] + len / 2];
classes[sa[i]] = same ? classes[sa[i - 1]] : i;
}
for (int i = 0; i < n; i++) {
int pos = sa[i] - len;
if (pos >= 0) {
sa[cnt[classes[pos]]++] = pos;
}
}
}
}
void kasai() {
int k = 0;
for (int i = 0; i < n; i++) {
inv_sa[sa[i]] = i;
}
for (int i = 0; i < n; i++) {
if (inv_sa[i] == n - 1) {
k = 0;
} else {
int j = sa[inv_sa[i] + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
lcp[inv_sa[i]] = k;
if (k) k--;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> s;
n = s.size();
manachers();
suffix_array();
kasai();
for (int i = 0; i < n; i++) {
ans = max<ll>(ans, 2 * d1[i] - 1);
ans = max<ll>(ans, 2 * d2[i]);
}
dsu.reset();
vector<array<int, 3>> ord;
for (int i = 0; i < n - 1; i++) {
ord.push_back({min({lcp[i], d1[sa[i]], d1[sa[i + 1]]}), i, i + 1});
}
sort(ord.rbegin(), ord.rend());
for (auto [sz, pos1, pos2] : ord) {
dsu.join(pos1, pos2);
ans = max(ans, 1LL * (2 * sz - 1) * dsu.sz[dsu.find(pos1)]);
}
dsu.reset();
ord.clear();
for (int i = 0; i < n - 1; i++) {
if (d2[sa[i]] == 0) continue;
int nxt = i + 1;
int common = lcp[i];
while (common && nxt < n && d2[sa[nxt]] == 0) {
common = min(lcp[nxt], common);
nxt++;
}
if (nxt < n) ord.push_back({min({common, d2[sa[i]], d2[sa[nxt]]}), i, nxt});
}
sort(ord.rbegin(), ord.rend());
for (auto [sz, pos1, pos2] : ord) {
dsu.join(pos1, pos2);
ans = max(ans, 2LL * sz * dsu.sz[dsu.find(pos1)]);
}
cout << ans << '\n';
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... |