이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; i++)
#define f0r(i, a) f1r(i, 0, a)
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto& a : x)
typedef string str;
template<class T> struct RMQ { // floor(log_2(x))
int level(int x) { return 31-__builtin_clz(x); }
vector<T> v; vector<vi> jmp;
int comb(int a, int b) { // index of min
return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); }
void init(const vector<T>& _v) {
v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
for (int j = 1; 1<<j <= sz(v); ++j) {
jmp.pb(vi(sz(v)-(1<<j)+1));
F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
jmp[j-1][i+(1<<(j-1))]);
}
}
int index(int l, int r) { // get index of min element
assert(l <= r); int d = level(r-l+1);
return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
T query(int l, int r) { return v[index(l,r)]; }
};
struct SuffixArray {
str S; int N; vi sa, isa, lcp;
void init(str _S) { N = sz(S = _S)+1; genSa(); genLcp(); }
void genSa() {
sa = isa = vi(N); sa[0] = N-1; iota(1+all(sa),0);
sort(1+all(sa),[&](int a, int b) { return S[a] < S[b]; });
FOR(i,1,N) { int a = sa[i-1], b = sa[i];
isa[b] = i > 1 && S[a] == S[b] ? isa[a] : i; }
for (int len = 1; len < N; len *= 2) { // currently sorted by first len chars
vi s(sa), is(isa), pos(N); iota(all(pos),0);
trav(t,s) { int T = t-len; if (T >= 0) sa[pos[isa[T]]++] = T; }
FOR(i,1,N) { int a = sa[i-1], b = sa[i];
isa[b] = is[a] == is[b] && is[a+len] == is[b+len] ? isa[a] : i; }
}
}
void genLcp() { // Kasai's Algo
lcp = vi(N-1); int h = 0;
F0R(b,N-1) { int a = sa[isa[b]-1];
while (a+h < sz(S) && S[a+h] == S[b+h]) h ++;
lcp[isa[b]-1] = h; if (h) h--; }
R.init(lcp); /// if we cut off first chars of two strings
/// with lcp h then remaining portions still have lcp h-1
}
RMQ<int> R;
int getLCP(int a, int b) { // lcp of suffixes starting at a,b
if (a == b) return sz(S)-a;
int l = isa[a], r = isa[b]; if (l > r) swap(l,r);
return R.query(l,r-1);
}
};
std::vector<int> manacher(std::string s) {
std::string t = "@";
for (auto& c : s)
t += c, t += '#';
t.back() = '&';
std::vector<int> res((int) t.size() - 1);
int lo = 0, hi = 0;
for (int i = 1; i < (int) t.size() - 1; i++) {
if (i != 1)
res[i] = std::min(hi - i, res[hi - i + lo]);
while (t[i - res[i] - 1] == t[i + res[i] + 1])
res[i]++;
if (i + res[i] > hi)
lo = i - res[i], hi = i + res[i];
}
res.erase(res.begin());
for (int i = 0; i < (int) res.size(); i++)
if ((i & 1) == (res[i] & 1))
res[i]++;
return res;
}
struct IntervalJoin {
std::vector<int> e;
std::vector<std::pair<int, int>> interval;
void init(int n) {
e = std::vector<int>(n, -1);
interval.resize(n);
for (int i = 0; i < n; i++) {
interval[i].first = interval[i].second = i;
}
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
bool same_set(int a, int b) {
return get(a) == get(b);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) std::swap(x, y);
interval[x].first = min(interval[x].first, interval[y].first);
interval[x].second = max(interval[x].second, interval[y].second);
e[x] += e[y]; e[y] = x;
return true;
}
std::pair<int, int> get_interval(int x) {
x = get(x);
return interval[x];
}
};
template <class T> struct BIT {
std::vector<T> bit;
int n;
void init(int n_) {
n = n_;
bit.resize(n);
}
void init(std::vector<T>& a) {
n = (int) a.size();
a.assign(n, 0);
for (int i = 0; i < (int) a.size(); i++) {
add(i, a[i]);
}
}
T sum(int r) {
T ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
return ret;
}
T query(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, T delta) {
for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
string s; cin >> s;
int n = sz(s);
SuffixArray S; S.init(s);
vector<int> m = manacher(s);
long long ans = 0;
for (ll x : m)
ans = max(ans, x);
{
vector<int> pal(n);
for (int i = 1; i < n; i++) {
pal[i] = m[2 * i - 1] / 2;
}
IntervalJoin I; I.init(n);
vector<vector<int>> bucket(n);
vector<vector<int>> gap(n);
for (int i = 0; i < n; i++) {
bucket[pal[i]].push_back(i);
}
for (int i = 0; i < n - 1; i++) {
int i1 = S.sa[i + 1];
int i2 = S.sa[i + 2];
int val = S.getLCP(i1, i2);
gap[val].push_back(i);
}
BIT<long long> bit;
bit.init(n);
for (int i = n - 1; i >= 0; i--) {
for (int x : bucket[i]) {
bit.add(S.isa[x] - 1, 1); // add 1 to a potential location
}
for (int x : gap[i]) {
I.unite(x, x + 1);
}
for (int x : bucket[i]) {
int y = S.isa[x]-1;
pi p = I.get_interval(y);
int res = bit.query(p.first, p.second);
ans = max(ans, 1LL * 2 * i * res);
}
}
}
{
vector<int> pal(n);
for (int i = 0; i < n; i++) {
pal[i] = m[2 * i] / 2;
}
vector<vector<int>> bucket(n);
vector<vector<int>> gap(n);
for (int i = 0; i < n; i++) {
bucket[pal[i]].push_back(i);
}
for (int i = 0; i < n - 1; i++) {
int i1 = S.sa[i + 1];
int i2 = S.sa[i + 2];
int val = S.getLCP(i1, i2);
if (val)
gap[val - 1].push_back(i);
}
IntervalJoin I; I.init(n);
BIT<long long> bit;
bit.init(n);
for (int i = n - 1; i >= 0; i--) {
for (int x : bucket[i]) {
bit.add(S.isa[x] - 1, 1);
}
for (int x : gap[i]) {
I.unite(x, x + 1);
}
for (int x : bucket[i]) {
int y = S.isa[x]-1;
pi p = I.get_interval(y);
int res = bit.query(p.first, p.second);
ans = max(ans, 1LL * (2 * i + 1) * res);
}
}
;
}
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... |