#include <bits/stdc++.h>
//#define TAMREF 1
using namespace std;
typedef long long ll;
const char g = 'a' + 26;
const ll o = 28LL;
const ll h[2] = {1000000007LL, 1610612741LL};
const ll io[2] = {35714286LL, 1323003323LL};
const int mx = 6e5 + 5;
ll ph[2][mx], iph[2][mx];
void init_hash(){
for(int b = 0; b < 2; b++){
ph[b][0] = 1;
iph[b][0] = 1;
for(int i = 1; i < mx; i++){
ph[b][i] = ph[b][i-1] * o % h[b];
if(i <= 2) iph[b][i] = iph[b][i-1] * io[b] % h[b];
}
}
}
char S[mx], P[mx];
int n, m;
void input(){
scanf("%s",P); m = strlen(P);
for(int i = 0; i < m; i++){
S[2*i] = g;
S[2*i+1] = P[i];
}
S[2*m] = g;
n = 2 * m + 1;
}
int R[mx];
void Manacher(){
int r = 0, j = 0;
for(int i = 1; i < n; i++){
int &h = R[i];
if(i <= r) h = min(r - i, R[2*j - i]);
while(i-h-1 >= 0 && i+h+1 < n && S[i-h-1] == S[i+h+1]) ++h;
if(i + h > r){
j = i;
r = i + h;
}
}
#ifdef TAMREF
puts(S);
for(int i = 0; i < n; i++) printf("%d ",R[i]);
puts("");
#endif
}
unordered_map<ll,int> I;
vector<int> cnt(1);
vector<int> len(1);
vector<vector<int>> gph(1);
vector<int> isRoot(1);
void Shrink(){
for(int i = 0; i < n; i++) S[i] -= 'a'-1;
for(int i = 1, s, e; i < n-1; i++){
if(!R[i]) continue;
s = i - R[i] + 1, e = i + R[i] - 1;
ll hv[2] = {0,0}, tmp;
int child_i = -1;
int tmp_i;
int flag_once = 1, keep_loop = 1;
for(int b = 0; b < 2; b++){
for(int j = s; j <= e; j++){
hv[b] = (hv[b] * o + S[j]) % h[b];
}
}
while(e >= s){
tmp = (hv[0] << 32 | hv[1]);
tmp_i = I[tmp];
if(!tmp_i){ //insert new hash value
#ifdef TAMREF
printf("%d-th HASH : [%d, %d],\nhash string = ",cnt.size(),s,e);
for(int j = s; j <= e; j++) printf("%c",S[j] + 'a' - 1);
puts("");
#endif // TAMREF
tmp_i = I[tmp] = cnt.size();
cnt.push_back(flag_once);
len.push_back((e-s)/2 + 1);
gph.push_back(vector<int>());
isRoot.push_back(1);
}else{
cnt[tmp_i] += flag_once;
keep_loop = 0;
}
flag_once = 0;
if(child_i != -1){
gph[tmp_i].push_back(child_i);
isRoot[child_i] = 0;
}
if(!keep_loop || e - 2 < s + 2) break;
child_i = tmp_i;
for(int b = 0; b < 2; b++){
hv[b] -= S[e] + o * S[e-1];
hv[b] -= (ph[b][e-s] * S[s] + ph[b][e-s-1] * S[s+1]) % h[b];
hv[b] = ((hv[b] % h[b] + h[b]) % h[b]) * iph[b][2] % h[b];
}
e -= 2;
s += 2;
}
}
}
int vis[mx];
ll ans = 1;
int dfs(int x){
#ifdef TAMREF
printf("dfs : %d\n",x);
#endif // TAMREF
ll c = cnt[x];
vis[x] = 1;
for(int &u : gph[x]){
if(!vis[u]) c += dfs(u);
}
ans = max(ans, c * len[x]);
return c;
}
void pro(){
int N = cnt.size();
for(int i = 1; i < N; i++){
#ifdef TAMREF
printf("%d - th node : cnt = %d, len = %d, isRoot = %d\n",i,cnt[i],len[i],isRoot[i]);
#endif // TAMREF
if(isRoot[i] && !vis[i]){
#ifdef TAMREF
printf("dfs start on %d\n",i);
#endif // TAMREF
dfs(i);
}
}
printf("%lld\n",ans);
}
int main(){
init_hash();
input();
Manacher();
Shrink();
pro();
}
Compilation message
palindrome.cpp: In function 'void input()':
palindrome.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",P); m = strlen(P);
~~~~~^~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
9720 KB |
Output is correct |
2 |
Correct |
16 ms |
9832 KB |
Output is correct |
3 |
Correct |
16 ms |
9832 KB |
Output is correct |
4 |
Correct |
17 ms |
9832 KB |
Output is correct |
5 |
Correct |
16 ms |
9832 KB |
Output is correct |
6 |
Correct |
16 ms |
9856 KB |
Output is correct |
7 |
Correct |
16 ms |
9864 KB |
Output is correct |
8 |
Correct |
16 ms |
10044 KB |
Output is correct |
9 |
Correct |
16 ms |
10044 KB |
Output is correct |
10 |
Correct |
16 ms |
10044 KB |
Output is correct |
11 |
Correct |
17 ms |
10044 KB |
Output is correct |
12 |
Correct |
16 ms |
10044 KB |
Output is correct |
13 |
Correct |
16 ms |
10044 KB |
Output is correct |
14 |
Correct |
16 ms |
10044 KB |
Output is correct |
15 |
Correct |
16 ms |
10044 KB |
Output is correct |
16 |
Correct |
16 ms |
10044 KB |
Output is correct |
17 |
Correct |
16 ms |
10044 KB |
Output is correct |
18 |
Correct |
16 ms |
10044 KB |
Output is correct |
19 |
Correct |
16 ms |
10044 KB |
Output is correct |
20 |
Correct |
16 ms |
10044 KB |
Output is correct |
21 |
Correct |
16 ms |
10044 KB |
Output is correct |
22 |
Correct |
16 ms |
10044 KB |
Output is correct |
23 |
Correct |
16 ms |
10044 KB |
Output is correct |
24 |
Correct |
16 ms |
10044 KB |
Output is correct |
25 |
Correct |
16 ms |
10044 KB |
Output is correct |
26 |
Correct |
16 ms |
10044 KB |
Output is correct |
27 |
Correct |
16 ms |
10044 KB |
Output is correct |
28 |
Correct |
16 ms |
10044 KB |
Output is correct |
29 |
Correct |
16 ms |
10044 KB |
Output is correct |
30 |
Correct |
16 ms |
10044 KB |
Output is correct |
31 |
Correct |
16 ms |
10044 KB |
Output is correct |
32 |
Correct |
16 ms |
10044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
10108 KB |
Output is correct |
2 |
Correct |
22 ms |
10108 KB |
Output is correct |
3 |
Correct |
42 ms |
10108 KB |
Output is correct |
4 |
Correct |
18 ms |
10108 KB |
Output is correct |
5 |
Correct |
41 ms |
10108 KB |
Output is correct |
6 |
Correct |
41 ms |
10168 KB |
Output is correct |
7 |
Correct |
17 ms |
10204 KB |
Output is correct |
8 |
Correct |
28 ms |
10204 KB |
Output is correct |
9 |
Correct |
18 ms |
10204 KB |
Output is correct |
10 |
Correct |
17 ms |
10204 KB |
Output is correct |
11 |
Correct |
17 ms |
10204 KB |
Output is correct |
12 |
Correct |
17 ms |
10204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1092 ms |
11320 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1091 ms |
12836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1079 ms |
14956 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |