#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = (ll) 1e9+9;
const ll base = 29;
int lg2[300005];
void prepLg2(int bound){
for(int i=2;i<=bound;i++)
lg2[i] = lg2[i>>1] + 1;
}
struct suffixArray{
vector <int> sa, saRank, tmp;
vector <vector <int> > lcp;
int strLen, gap;
bool saCmp(int x,int y){
if (saRank[x] != saRank[y])
return saRank[x] < saRank[y];
return x+gap < strLen && y+gap < strLen ? saRank[x+gap] < saRank[y+gap] : x > y;
}
void build_lcp(string &s){
int k = 0;
for(int i = 0; i < strLen; i ++){
if (saRank[i] != strLen - 1){
for (int j = sa[saRank[i] + 1]; max(i+k, j+k) < strLen && s[i + k] == s[j + k];) ++k;
lcp[saRank[i]][0] = k;
if (k) k--;
}
}
for(int k = 1; k < 20; k ++){
for(int i = 0; i < strLen; i ++)
if (i + (1<<k) < strLen)
lcp[i][k] = min(lcp[i][k-1], lcp[i+(1<<(k-1))][k-1]);
else break;
}
}
int getLcp(int l,int r){
if (l > r) swap(l, r);
if (l == r) return strLen - sa[l];
int k = lg2[r - l];
return min(lcp[l][k], lcp[r-(1<<k)][k]);
}
void build(string &s, int isIndexFromOne = 0){
strLen = s.size();
sa.assign(strLen + 5, 0);
saRank.assign(strLen + 5, 0);
tmp.assign(strLen + 5, 0);
lcp.assign(strLen + 5, vector<int>(20));
//for(int i = 0; i < strLen; i ++)
// lcp[i].assign(20, 0);
for(int i = 0; i < strLen; i ++)
sa[i] = i, saRank[i] = s[i];
for(gap = 1;;gap *= 2){
sort(sa.begin(), sa.begin() + strLen, [&](int a, int b) {return this->saCmp(a, b);});
//sort(sa.begin(), sa.begin() + strLen, saCmp);
for(int i = 0; i < strLen; i ++) tmp[i+1] = tmp[i] + saCmp(sa[i], sa[i+1]);
for(int i = 0; i < strLen; i ++) saRank[sa[i]] = tmp[i];
if (tmp[strLen-1] == strLen-1) break;
}
build_lcp(s);
}
};
int n;
string s[2];
suffixArray suff;
ll hashCode[2][300000], pBase[300000];
void prepHash(){
pBase[0] = 1;
for(int i=1;i<300000;i++)
pBase[i] = pBase[i-1] * base % mod;
hashCode[0][0] = s[0][0] - 'a' + 1;
hashCode[1][0] = s[1][0] - 'a' + 1;
for(int i=1;i<n;i++)
hashCode[0][i] = (hashCode[0][i-1] + pBase[i] * (s[0][i] - 'a')) % mod,
hashCode[1][i] = (hashCode[1][i-1] + pBase[i] * (s[1][i] - 'a')) % mod;
}
bool checkPalindrome(int l1,int r1){
int l2 = n-1-r1;
int r2 = n-1-l1;
ll val1 = (hashCode[0][r1] - (l1 == 0 ? 0 : hashCode[0][l1-1]) + mod) % mod;
ll val2 = (hashCode[1][r2] - (l2 == 0 ? 0 : hashCode[1][l2-1]) + mod) % mod;
val1 = val1 * pBase[max(0, r2 - r1)] % mod;
val2 = val2 * pBase[max(0, r1 - r2)] % mod;
return val1 == val2;
}
long long solve(int i, int sz) {
int id = suff.saRank[i], res = 0;
int l = 0, r = id;
while(l < r) {
int mid = (l + r) >> 1;
if(suff.getLcp(mid, id) >= sz) r = mid;
else l = mid + 1;
}
res += id - l + 1;
l = id, r = n - 1;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(suff.getLcp(id, mid) >= sz) l = mid;
else r = mid - 1;
}
res += l - id;
return 1LL * res * sz;
}
int main(){
prepLg2(300000);
iostream::sync_with_stdio(0);
cin >> s[0];
n = s[0].size();
s[1] = s[0];
reverse(s[1].begin(), s[1].end());
suff.build(s[0]);
prepHash();
int sz0, sz1;
sz0 = 0, sz1 = 1;
long long ans = 0;
for(int i = n - 1; i >= 0; --i) {
int p0 = i + 2 * sz0 - 1;
int p1 = i + 2 * sz1 - 2;
if(p0 > p1) ans = max(ans, solve(i, p0 - i + 1));
else ans = max(ans, solve(i, p1 - i + 1));
if(i == 0) continue;
sz0++, sz1++;
while(sz0) {
p0 = i - 1 + 2 * sz0 - 1;
if(!checkPalindrome(i - 1, p0)) sz0--;
else break;
}
while(sz1) {
p1 = i - 1 + 2 * sz1 - 2;
if(!checkPalindrome(i - 1, p1)) sz1--;
else break;
}
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3832 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
3944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4012 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4012 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4012 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4140 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4192 KB |
Output is correct |
| 6 |
Correct |
7 ms |
4224 KB |
Output is correct |
| 7 |
Incorrect |
7 ms |
4224 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
5588 KB |
Output is correct |
| 2 |
Correct |
23 ms |
5604 KB |
Output is correct |
| 3 |
Correct |
16 ms |
5604 KB |
Output is correct |
| 4 |
Correct |
16 ms |
5604 KB |
Output is correct |
| 5 |
Correct |
18 ms |
5732 KB |
Output is correct |
| 6 |
Correct |
17 ms |
5732 KB |
Output is correct |
| 7 |
Correct |
15 ms |
5732 KB |
Output is correct |
| 8 |
Correct |
18 ms |
5740 KB |
Output is correct |
| 9 |
Correct |
16 ms |
5740 KB |
Output is correct |
| 10 |
Correct |
18 ms |
5740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
18904 KB |
Output is correct |
| 2 |
Correct |
173 ms |
18904 KB |
Output is correct |
| 3 |
Correct |
180 ms |
18904 KB |
Output is correct |
| 4 |
Correct |
158 ms |
18904 KB |
Output is correct |
| 5 |
Correct |
248 ms |
18904 KB |
Output is correct |
| 6 |
Correct |
211 ms |
18904 KB |
Output is correct |
| 7 |
Correct |
167 ms |
18904 KB |
Output is correct |
| 8 |
Correct |
204 ms |
18904 KB |
Output is correct |
| 9 |
Correct |
257 ms |
18904 KB |
Output is correct |
| 10 |
Correct |
273 ms |
18940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
810 ms |
48152 KB |
Output is correct |
| 2 |
Correct |
642 ms |
48152 KB |
Output is correct |
| 3 |
Correct |
735 ms |
48388 KB |
Output is correct |
| 4 |
Correct |
651 ms |
48596 KB |
Output is correct |
| 5 |
Execution timed out |
1084 ms |
48928 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
