#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 10;
int base[2] = {313, 369}, mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
int pw[maxn][2];
struct HSH{
int hsh[maxn][2];
HSH(){};
HSH(string s){
memset(hsh, 0, sizeof hsh);
int n = s.size();
for (int i = 1; i <= n; i++){
for (int j = 0; j < 2; j++){
hsh[i][j] = (1ll * hsh[i-1][j] * base[j] + s[i-1] - 'a' + 1) % mod[j];
}
}
}
pii gethsh(int l, int r){
l--;
int res[2];
for (int i = 0; i < 2; i++){
res[i] = (1ll * hsh[r][i] - 1ll * hsh[l][i] * pw[r-l][i] % mod[i] + 1ll * mod[i]) % mod[i];
}
return {res[0], res[1]};
}
};
int n, suf[maxn], rnk[maxn << 1], tmp[maxn], lcp[maxn], dsu[maxn], a[maxn], cnt[maxn];
int W = 1;
string s;
int getdsu(int v){
return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}
void merge(int u, int v){
u = getdsu(u);
v = getdsu(v);
dsu[v] = u;
cnt[u] += cnt[v];
}
bool scmp(int x, int y){
return (rnk[x] == rnk[y]? rnk[x+W] < rnk[y+W]: rnk[x] < rnk[y]);
}
void suffarr(string &s){
int n = s.size();
for (int i = 0; i < n; i++){
rnk[i] = s[i] - 'a' + 1;
suf[i] = i;
}
for (;; W <<= 1){
sort(suf, suf + n, scmp);
tmp[suf[0]] = 1;
for (int i = 1; i < n; i++){
tmp[suf[i]] = tmp[suf[i-1]] + scmp(suf[i-1], suf[i]);
}
for (int i = 0; i < n; i++) rnk[i] = tmp[i];
if (rnk[suf[n-1]] == n) return;
}
}
void buildlcp(string &s){
int n = s.size();
int k = 0;
for (int i = 0; i < n; i++){
if (i + k < n && suf[rnk[i]] + k < n && s[i+k] == s[suf[rnk[i]]+k]) k++;
lcp[rnk[i]] = k;
if (k) k--;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
pw[0][0] = pw[0][1] = 1;
for (int i = 1; i < maxn; i++){
for (int j = 0; j < 2; j++){
pw[i][j] = 1ll * pw[i-1][j] * base[j] % mod[j];
}
}
cin >> s;
string t = s;
reverse(all(t));
HSH S(s);
HSH T(t);
n = s.size();
suffarr(s);
buildlcp(s);
for (int i = 1; i <= n; i++){
int l = 0, r = min(i, n-i+2);
while(l + 1 < r){
int mid = (l + r) >> 1;
int tmp = n + 2 - i;
if (S.gethsh(i-mid, i+mid-1) == T.gethsh(tmp-mid, tmp+mid-1)) l = mid;
else r = mid;
}
a[i] = l;
}
vector<pair<pii,int>> Q;
for (int i = 1; i <= n; i++){
if (i != n) Q.push_back({{lcp[i], i}, 1});
Q.push_back({{a[i], rnk[i-1]}, 2});
}
memset(dsu, -1, sizeof dsu);
memset(cnt, 0, sizeof cnt);
sort(all(Q), greater<pair<pii,int>>());
ll ans = 0;
for (auto [x, y]: Q){
if (y == 1){
merge(x.S, x.S + 1);
int v = getdsu(x.S);
ans = max(ans, 2ll * cnt[v] * x.F);
}
else{
int v = getdsu(x.S);
cnt[v]++;
ans = max(ans, 2ll * cnt[v] * x.F);
}
}
for (int i = 1; i <= n; i++){
int l = 0, r = min(i, n-i+1);
while(l + 1 < r){
int mid = (l + r) >> 1;
int tmp = n + 1 - i;
if (S.gethsh(i-mid, i+mid) == T.gethsh(tmp-mid, tmp+mid)) l = mid;
else r = mid;
}
a[i] = l+1;
}
Q.clear();
for (int i = 1; i <= n; i++){
if (i != n) Q.push_back({{lcp[i], i}, 1});
Q.push_back({{a[i], rnk[i-1]}, 2});
}
memset(dsu, -1, sizeof dsu);
memset(cnt, 0, sizeof cnt);
sort(all(Q), greater<pair<pii,int>>());
for (auto [x, y]: Q){
if (y == 1){
merge(x.S, x.S + 1);
int v = getdsu(x.S);
ans = max(ans, 1ll * (2 * x.F - 1) * cnt[v]);
}
else{
int v = getdsu(x.S);
cnt[v]++;
ans = max(ans, 1ll * (2 * x.F - 1) * cnt[v]);
}
}
cout << ans << '\n';
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | for (auto [x, y]: Q){
| ^
palindrome.cpp:189:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
189 | for (auto [x, y]: Q){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9672 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9628 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
10324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
14964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
754 ms |
26788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
