#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, p = 31, maxn = 3e5 + 1;
struct Modint {
int x;
Modint() { x = 0; }
Modint(int _x) {
while (_x >= mod) { _x -= mod; }
while (_x < 0) { _x += mod; }
x = _x;
}
Modint(long long _x) {
if (_x >= mod || _x <= -mod) { _x %= mod; }
if (_x < 0) { _x += mod; }
x = _x;
}
Modint operator+(const Modint& other) const {
return Modint(x + other.x);
}
Modint operator-(const Modint& other) const {
return Modint(x - other.x);
}
Modint operator*(const Modint& other) const {
return Modint(x * 1ll * other.x);
}
void operator+=(const Modint& other) {
*this = *this + other;
}
void operator-=(const Modint& other) {
*this = *this - other;
}
void operator*=(const Modint& other) {
*this = *this * other;
}
~Modint() {}
};
Modint pExp[maxn];
struct DSU {
int n, maxcompsz;
vector<int> par, sz;
DSU() {}
DSU(int _n) {
n = _n, maxcompsz = 0;
par.resize(n);
sz.resize(n);
clear();
}
void clear() {
maxcompsz = 0;
for (int i = 0; i < n; ++i) {
par[i] = -1, sz[i] = 0;
}
}
void create(int i) {
par[i] = i, sz[i] = 1;
maxcompsz = max(maxcompsz, 1);
}
int getParent(int v) {
if (par[v] != v) {
par[v] = getParent(par[v]);
}
return par[v];
}
void uniteSets(int v, int u) {
v = getParent(v), u = getParent(u);
if (v == u) {
return;
}
sz[v] += sz[u];
par[u] = v;
maxcompsz = max(maxcompsz, sz[v]);
}
~DSU() {}
};
int posOf[maxn];
void countSort(vector<int>& a, vector<int>& tmp, const vector<int>& c) {
int n = a.size();
for (int i = 0; i < n; ++i) {
posOf[i] = 0;
}
for (const int& x : c) {
++posOf[x];
}
for (int i = n - 1, pref = n; i >= 0; --i) {
pref -= posOf[i];
posOf[i] = pref;
}
for (const int& x : a) {
tmp[posOf[c[x]]++] = x;
}
swap(a, tmp);
}
void buildSufArr(const string& s, vector<int>& sufArr, vector<int>& c) {
int n = s.size();
for (int i = 0; i < n; ++i) {
sufArr[i] = i;
}
sort(sufArr.begin(), sufArr.end(), [&](const int& A, const int& B) {
return s[A] < s[B];
});
c[sufArr[0]] = 0;
for (int i = 1; i < n; ++i) {
c[sufArr[i]] = c[sufArr[i - 1]];
if (s[sufArr[i - 1]] != s[sufArr[i]]) {
++c[sufArr[i]];
}
}
vector<int> tmp(n);
for (int k = 0; (1 << k) < n; ++k) {
for (int i = 0; i < n; ++i) {
sufArr[i] -= (1 << k);
if (sufArr[i] < 0) {
sufArr[i] += n;
}
}
countSort(sufArr, tmp, c);
tmp[sufArr[0]] = 0;
for (int i = 1; i < n; ++i) {
tmp[sufArr[i]] = tmp[sufArr[i - 1]];
int nxtprev = sufArr[i - 1] + (1 << k);
if (nxtprev >= n) { nxtprev -= n; }
int nxtcur = sufArr[i] + (1 << k);
if (nxtcur >= n) { nxtcur -= n; }
if (c[sufArr[i - 1]] != c[sufArr[i]] || c[nxtprev] != c[nxtcur]) {
++tmp[sufArr[i]];
}
}
swap(c, tmp);
}
}
vector<Modint> h, revH;
string s;
bool equalOne(int l1, int r1, int l2, int r2) {
int val1 = ((h[r1 + 1] - h[l1]) * pExp[(int)h.size() - 2 - r1]).x;
int val2 = ((h[r2 + 1] - h[l2]) * pExp[(int)h.size() - 2 - r2]).x;
return val1 == val2;
}
int getLcp(int i, int j) {
int left = 0, right = (int)s.size() - max(i, j);
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (equalOne(i, i + mid - 1, j, j + mid - 1)) {
left = mid;
} else {
right = mid;
}
}
return left;
}
/*void buildLcp(const string& s, vector<int>& sufArr, vector<int>& c, vector<int>& lcp) {
lcp[0] = 0;
for (int i = 1; i < (int)s.size() - 1; ++i) {
int ptr = sufArr[i], j = sufArr[i + 1];
int left = 0, right = (int)s.size() - max(ptr, j);
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (equalOne(ptr, ptr + mid - 1, j, j + mid - 1)) {
left = mid;
} else {
right = mid;
}
}
lcp[i] = left;
}
}*/
bool equal(int l1, int r1, int l2, int r2) {
int val1 = ((h[r1 + 1] - h[l1]) * pExp[(int)h.size() - 2 - r1]).x;
int val2 = ((revH[l2] - revH[r2 + 1]) * pExp[l2]).x;
return val1 == val2;
}
//sparse Table
void solve() {
cin >> s;
int n = s.size();
h.resize(n + 1);
for (int i = 0; i < n; ++i) {
h[i + 1] = h[i] + pExp[i] * (s[i] - 'a' + 1);
}
revH.resize(n + 1);
for (int i = n - 1; i >= 0; --i) {
revH[i] = revH[i + 1] + pExp[n - 1 - i] * (s[i] - 'a' + 1);
// cerr << "i: " << i << ", revH: " << revH[i].x << '\n';
}
vector<int> odd(n), even(n);
// even
for (int i = 0; i < n; ++i) {
int left = 0, right = min(i, n - i) + 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (equal(i - mid, i - 1, i, i + mid - 1)) {
left = mid;
} else {
right = mid;
}
}
even[i] = left;
// cerr << "i: " << i << ", even: " << even[i] << '\n';
}
// odd
for (int i = 0; i < n; ++i) {
int left = 0, right = min(i + 1, n - i) + 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (equal(i - mid + 1, i, i, i + mid - 1)) {
left = mid;
} else {
right = mid;
}
}
odd[i] = left;
// cerr << "i: " << i << ", odd: " << odd[i] << '\n';
}
s += '#';
++n;
vector<int> sufArr(n), c(n);
buildSufArr(s, sufArr, c);
/*for (int i = 0; i < n; ++i) {
cerr << sufArr[i] << ' ';
}
cerr << '\n';
for (int i = 0; i < n; ++i) {
cerr << c[i] << ' ';
}
cerr << '\n';*/
vector<pair<int, int>> evs(n - 1);
long long ans = 0;
DSU dsu(n);
set<int> alive;
// even lengths
for (int i = 0; i < n - 1; ++i) {
evs[i] = {2 * even[i], i};
}
sort(evs.rbegin(), evs.rend());
for (int len = n / 2 * 2, ptr = 0; len > 0; len -= 2) {
while (ptr < (int)evs.size() && evs[ptr].first == len) {
int i = evs[ptr].second;
// cerr << "i: " << i << '\n';
// cerr << "c: " << c[i] << '\n';
dsu.create(i);
auto it = alive.emplace(c[i]).first;
if (it != alive.begin()) {
auto prv = prev(it);
// cerr << "i: " << i << ", sufArr: " << sufArr[*prv] << '\n';
while (getLcp(sufArr[*prv], i) * 2 >= len) {
// cerr << "merge: " << *prv << '\n';
dsu.uniteSets(i, sufArr[*prv]);
prv = alive.erase(prv);
if (prv == alive.begin()) {
break;
} else {
prv = prev(prv);
}
}
}
if (*it != *alive.rbegin()) {
auto nxt = next(it);
// cerr << "i: " << i << ", sufArr: " << sufArr[*nxt] << '\n';
while (getLcp(sufArr[*nxt], i) * 2 >= len) {
dsu.uniteSets(i, sufArr[*nxt]);
nxt = alive.erase(nxt);
if (nxt == alive.end()) {
break;
}
}
}
++ptr;
}
// cerr << "len: " << len << ", sz: " << dsu.maxcompsz << '\n';
ans = max(ans, dsu.maxcompsz * 1ll * len);
}
// odd lengths
dsu.clear();
alive.clear();
for (int i = 0; i < n - 1; ++i) {
evs[i] = {2 * odd[i] - 1, i};
}
sort(evs.rbegin(), evs.rend());
for (int len = (n % 2 == 0 ? n - 1 : n), ptr = 0; len > 0; len -= 2) {
while (ptr < (int)evs.size() && evs[ptr].first == len) {
int i = evs[ptr].second;
dsu.create(i);
auto it = alive.emplace(c[i]).first;
if (it != alive.begin()) {
auto prv = prev(it);
// cerr << "i: " << i << ", sufArr: " << sufArr[*prv] << '\n';
while (getLcp(sufArr[*prv], i) * 2 - 1 >= len) {
// cerr << "merge: " << *prv << '\n';
dsu.uniteSets(i, sufArr[*prv]);
prv = alive.erase(prv);
if (prv == alive.begin()) {
break;
} else {
prv = prev(prv);
}
}
}
if (*it != *alive.rbegin()) {
auto nxt = next(it);
// cerr << "i: " << i << ", sufArr: " << sufArr[*nxt] << '\n';
while (getLcp(sufArr[*nxt], i) * 2 - 1 >= len) {
dsu.uniteSets(i, sufArr[*nxt]);
nxt = alive.erase(nxt);
if (nxt == alive.end()) {
break;
}
}
}
++ptr;
}
// cerr << "len: " << len << ", sz: " << dsu.maxcompsz << '\n';
ans = max(ans, dsu.maxcompsz * 1ll * len);
}
cout << ans << '\n';
/*vector<int> lcp(n - 1);
buildLcp(s, sufArr, c, lcp);*/
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pExp[0] = 1;
for (int i = 1; i < maxn; ++i) {
pExp[i] = pExp[i - 1] * p;
}
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 17 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 23 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 28 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 30 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 31 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 32 |
Correct |
2 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
14 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
15 ms |
3116 KB |
Output is correct |
| 5 |
Correct |
14 ms |
2904 KB |
Output is correct |
| 6 |
Correct |
14 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2904 KB |
Output is correct |
| 8 |
Correct |
16 ms |
2904 KB |
Output is correct |
| 9 |
Correct |
18 ms |
3072 KB |
Output is correct |
| 10 |
Correct |
18 ms |
3176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
6856 KB |
Output is correct |
| 2 |
Correct |
154 ms |
6872 KB |
Output is correct |
| 3 |
Correct |
152 ms |
6856 KB |
Output is correct |
| 4 |
Correct |
191 ms |
6936 KB |
Output is correct |
| 5 |
Correct |
194 ms |
6908 KB |
Output is correct |
| 6 |
Correct |
177 ms |
6856 KB |
Output is correct |
| 7 |
Correct |
215 ms |
6944 KB |
Output is correct |
| 8 |
Correct |
182 ms |
6852 KB |
Output is correct |
| 9 |
Correct |
174 ms |
6940 KB |
Output is correct |
| 10 |
Correct |
224 ms |
7104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
476 ms |
14784 KB |
Output is correct |
| 2 |
Correct |
561 ms |
14980 KB |
Output is correct |
| 3 |
Correct |
497 ms |
14836 KB |
Output is correct |
| 4 |
Correct |
763 ms |
14916 KB |
Output is correct |
| 5 |
Correct |
627 ms |
14656 KB |
Output is correct |
| 6 |
Correct |
646 ms |
14660 KB |
Output is correct |
| 7 |
Correct |
742 ms |
14660 KB |
Output is correct |
| 8 |
Correct |
617 ms |
14872 KB |
Output is correct |
| 9 |
Correct |
613 ms |
14920 KB |
Output is correct |
| 10 |
Correct |
801 ms |
14664 KB |
Output is correct |
| 11 |
Correct |
465 ms |
14776 KB |
Output is correct |
| 12 |
Correct |
602 ms |
14920 KB |
Output is correct |
