#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
struct SA {
static vector<int> sa, ord, lcp, table;
static vector<vector<int>> sp;
static int mod_sum(int x, int n) {
return x >= n ? x - n : x;
}
static void suffix_array(string& s) {
s += "$";
int n = s.size();
vector<int> tmpSA(n), tmpOrd(n), cnt(max(128, n), 0);
sa.resize(n);
ord.resize(n);
for(char ch : s) ++cnt[ch];
for(int i = 1; i < 128; ++i) cnt[i] += cnt[i - 1];
for(int i = 0; i < n; ++i) sa[--cnt[s[i]]] = i;
ord[sa[0]] = 0;
for(int i = 1; i < n; ++i) {
int pre = sa[i - 1], cur = sa[i];
ord[cur] = ord[pre] + (s[cur] != s[pre]);
}
int m = ord[sa[n - 1]] + 1;
for(int l = 0; (1 << l) < n; ++l) {
fill(cnt.begin(), cnt.begin() + m, 0);
for(int i = 0; i < n; ++i) ++cnt[ord[i]];
for(int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
for(int i = n - 1; i >= 0; --i) {
int j = mod_sum(sa[i] - (1 << l) + n, n);
tmpSA[--cnt[ord[j]]] = j;
}
tmpOrd[tmpSA[0]] = 0;
for(int i = 1; i < n; ++i) {
int pre = tmpSA[i - 1], cur = tmpSA[i];
auto x = make_pair(ord[pre], ord[mod_sum(pre + (1 << l), n)]);
auto y = make_pair(ord[cur], ord[mod_sum(cur + (1 << l), n)]);
tmpOrd[cur] = tmpOrd[pre] + (x != y);
}
swap(sa, tmpSA);
swap(ord, tmpOrd);
m = ord[sa[n - 1]] + 1;
}
s.pop_back();
sa.erase(sa.begin());
}
static void buildLCP(string& s) {
int n = s.size(), match = 0;
suffix_array(s);
table.resize(n);
lcp.resize(n);
for(int i = 0; i < n; ++i) table[sa[i]] = i;
for(int i = 0; i < n; ++i) {
if(table[i]) {
int k = i + match, j = sa[table[i] - 1] + match;
while(k < n && j < n && s[k] == s[j]) ++k, ++j;
match = k - i;
}
lcp[table[i]] = match;
match = max(0, match - 1);
}
int lg = 32 - __builtin_clz(n);
sp = vector<vector<int>>(lg, vector<int>(n));
for(int i = 0; i < n; ++i) sp[0][i] = lcp[i];
for(int i = 1; i < lg; ++i)
for(int j = 0; j + (1 << i) <= n; ++j)
sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
static int LCP(int i, int j) {
int k = (int)sa.size() - i;
i = table[i], j = table[j];
if(i > j) swap(i, j);
if(++i > j) return k;
k = 31 - __builtin_clz(j - i + 1);
return min(sp[k][i], sp[k][j - (1 << k) + 1]);
}
static int count(int l, int r) {
int L = table[l], R = table[l], n = sa.size();
for(int i = 31 - __builtin_clz(n); i >= 0; --i) {
int _L = L - (1 << i), _R = R + (1 << i);
if(_L >= 0 && LCP(sa[_L], l) >= r - l + 1) L = _L;
if(_R < n && LCP(sa[_R], l) >= r - l + 1) R = _R;
}
return R - L + 1;
}
};
vector<int> SA :: sa;
vector<int> SA :: ord;
vector<int> SA :: lcp;
vector<int> SA :: table;
vector<vector<int>> SA :: sp;
void manacher(string& s, vector<int>& d1, vector<int>& d2) {
int l = 0, r = -1, n = s.size();
d1.assign(n, 1);
d2.assign(n, 0);
for(int i = 0; i < n; ++i) {
if(i <= r) {
d1[i] = min(d1[l + r - i], r - i + 1);
d2[i] = min(d2[l + r - i + 1], r - i + 1);
}
while(i + d1[i] < n && i - d1[i] >= 0 && s[i - d1[i]] == s[i + d1[i]]) ++d1[i];
while(i + d2[i] < n && i - d2[i] - 1 >= 0 && s[i - d2[i] - 1] == s[i + d2[i]]) ++d2[i];
if(r < i + d2[i] - 1) l = i - d2[i], r = i + d2[i] - 1;
if(r < i + d1[i] - 1) l = i - d1[i] + 1, r = i + d1[i] - 1;
}
}
void solve() {
string s;
i64 ans = 0;
cin >> s;
int n = s.size();
vector<int> d1, d2;
manacher(s, d1, d2);
SA :: buildLCP(s);
int lg = 31 - __builtin_clz(n);
for(int i = 0; i < n; ++i) {
int m = 0;
for(int j = lg; j >= 0; --j) {
int _m = m + (1 << j);
int l = i - _m;
if(_m > d1[i]) continue;
int x = SA :: table[l];
if(!x) continue;
int y = SA :: sa[x - 1];
if(SA :: LCP(y, l) >= 2 * _m - 1) m = _m;
}
for(; m <= d1[i]; ++m)
ans = max(ans, (2ll * m - 1) * SA :: count(i - m, i + m));
}
for(int i = 0; i < n; ++i) {
if(!d2[i]) continue;
int m = 1;
for(int j = lg; j >= 0; --j) {
int _m = m + (1 << j);
int l = i - _m;
if(_m > d1[i]) continue;
int x = SA :: table[l];
if(!x) continue;
int y = SA :: sa[x - 1];
if(SA :: LCP(y, l) >= 2 * _m) m = _m;
}
for(; m <= d2[i]; ++m)
ans = max(ans, 2ll * m * SA :: count(i - m, i + m - 1));
}
cout << ans << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
316 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
10056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
31436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
