# include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 2;
const int mod = 1e9 + 9;
int n, bor[26][N], cnt[N * 27], used[26], cn = 1;
long long ans, h[N], pr = 101, pw[N];
string s;
map <int, int> mp;
int get(int l, int r){
long long hs = (h[r] - h[l - 1] + mod) % mod;
hs = (hs * pw[N - l]) % mod;
return hs;
}
void add(int v, int id, int len, int c){
while(1){
if(id - len <= 0 || id + len + c > n || s[id - len] != s[id + len + c]){
break;
}
int now = s[id - len] - 'a';
if(!bor[now][v]){
bor[now][v] = ++ cn;
}
v = bor[now][v];
mp[get(id - len, id)] = v;
len ++;
}
cnt[v] ++;
}
void f(int v, int len, int c){
for(int i = 0; i < 26; i ++){
if(bor[i][v]){
f(bor[i][v], len + 1, c);
cnt[v] += cnt[bor[i][v]];
}
}
ans = max(ans, (len * 2 - c) * 1ll * cnt[v]);
}
int main(){
cin >> s;
n = s.size();
s = ' ' + s;
pw[0] = pr;
for(int i = 1; i < N; i ++)
pw[i] = (pw[i - 1] * pr) % mod;
for(int i = 1; i <= n; i ++){
h[i] = (h[i - 1] + (s[i] - 'a' + 1) * pw[i]) % mod;
}
for(int i = 1; i <= n; i ++){
if(!used[s[i] - 'a']){
used[s[i] - 'a'] = 1;
add(1, i, 0, 0);
continue;
}
int lo = max(1, i - (n - i)), hi = i, pos;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(mp[get(md, i)])
hi = md - 1, pos = md;
else
lo = md + 1;
}
add(mp[get(pos, i)], i, i - pos + 1, 0);
}
f(1, 0, 1);
memset(bor, 0, sizeof(bor));
memset(cnt, 0, sizeof(cnt));
memset(used, 0, sizeof(used));
cn = 1;
mp.clear();
for(int i = 1; i < n; i ++){
if(s[i] != s[i + 1])
continue;
if(!used[s[i] - 'a']){
used[s[i] - 'a'] = 1;
add(1, i, 0, 1);
continue;
}
int lo = max(1, i - (n - i - 1)), hi = i, pos;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(mp[get(md, i)])
hi = md - 1, pos = md;
else
lo = md + 1;
}
add(mp[get(pos, i)], i, i - pos + 1, 1);
}
f(1, 0, 0);
cout << ans << endl;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
hs = (hs * pw[N - l]) % mod;
~~^~~
palindrome.cpp:83:55: note: 'pos' was declared here
int lo = max(1, i - (n - i - 1)), hi = i, pos;
^~~
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
hs = (hs * pw[N - l]) % mod;
~~^~~
palindrome.cpp:59:51: note: 'pos' was declared here
int lo = max(1, i - (n - i)), hi = i, pos;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
64888 KB |
Output is correct |
2 |
Correct |
53 ms |
64888 KB |
Output is correct |
3 |
Correct |
54 ms |
65016 KB |
Output is correct |
4 |
Correct |
54 ms |
64888 KB |
Output is correct |
5 |
Correct |
56 ms |
65016 KB |
Output is correct |
6 |
Correct |
55 ms |
64848 KB |
Output is correct |
7 |
Correct |
54 ms |
64888 KB |
Output is correct |
8 |
Correct |
56 ms |
64916 KB |
Output is correct |
9 |
Correct |
62 ms |
64888 KB |
Output is correct |
10 |
Incorrect |
54 ms |
64888 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
65060 KB |
Output is correct |
2 |
Incorrect |
58 ms |
65028 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
65884 KB |
Output is correct |
2 |
Incorrect |
90 ms |
66624 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
710 ms |
73720 KB |
Output is correct |
2 |
Incorrect |
840 ms |
79620 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1057 ms |
20048 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |