#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
char str[600005];
int n;
int dp[600005];
void manacher(){
int max_val = 0, pos = 0;
for (int i=1; i<=n; i++) {
int ret = i;
if(max_val >= i){
ret = min(max_val,i + dp[2 * pos - i]);
}
while (ret+1<=n && 2*i-ret-1> 0 && str[ret+1] == str[2*i-ret-1]){
ret++;
}
dp[i] = ret - i;
if(ret > max_val){
pos = i, ret = max_val;
}
}
for (int i=1; i<=n; i++) {
if(i%2 == 0) dp[i]++;
dp[i] /= 2;
}
}
const int prime = 1e9 + 9;
long long hs[300005], pw[300005];
unordered_map<long long,int> len, cnt, num;
unordered_map<long long,long long> nxt;
vector<long long> hash_candidate;
int piv;
long long get_hash(int s, int e){
return hs[e] - hs[s-1] * pw[e - s + 1];
}
void shrink(int s, int e, long long pa){
if(s > e) return;
long long par = 0;
num[0] = 0;
cnt[get_hash(s,e)]++;
while (s <= e) {
long long hsh = get_hash(s,e);
hash_candidate.push_back(hsh);
if(par) nxt[par] = hsh;
if(len.find(hsh) == len.end()){
len[hsh] = e - s + 1;
num[hsh] = ++piv;
}
else break;
par = hsh;
s++;
e--;
}
}
int tpar[300005], tcnt[300005], tlen[300005];
vector<int> graph[300005];
int subsize[300005];
long long ret;
int dfs(int x, int pa){
int r = tcnt[x];
for (int i=0; i<graph[x].size(); i++) {
if(graph[x][i] == pa) continue;
r += dfs(graph[x][i],x);
}
subsize[x] = r;
// printf("%d %d\n",subsize[x],tlen[x]);
ret = max(ret,1ll * subsize[x] * tlen[x]);
return r;
}
void make_tree(){
for (long long i : hash_candidate){
tpar[num[i]] = num[nxt[i]];
tcnt[num[i]] = cnt[i];
tlen[num[i]] = len[i];
}
for (int i=0; i<=piv; i++) {
if (i == tpar[i]) continue;
graph[i].push_back(tpar[i]);
graph[tpar[i]].push_back(i);
}
dfs(0,-1);
}
int main(){
scanf("%s",str);
n = (int)strlen(str);
for (int i=n-1; i>=0; i--) {
str[2*i+1] = str[i];
str[2*i] = ' ';
}
n = 2 * n - 1;
str[0] = 0;
manacher();
pw[0] = 1;
for (int i=1; i<=(n+1)/2; i++) {
hs[i] = hs[i-1] * prime + str[2*i-1];
pw[i] = pw[i-1] * prime;
}
for (int i=1; i<=n; i++) {
if(i % 2 == 1){
shrink((i+1)/2 - dp[i],(i+1)/2 + dp[i],0);
}
else{
shrink(i/2 + 1 - dp[i], i/2 + dp[i],0);
}
}
make_tree();
printf("%lld",ret);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '7' |
2 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '4' |
3 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '9' |
4 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '1' |
5 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '1' |
6 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '2' |
7 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '3' |
8 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '3' |
9 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '15' |
10 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '24' |
11 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '10' |
12 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '24' |
13 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '25' |
14 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '28' |
15 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '2' |
16 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '1' |
17 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '15' |
18 |
Correct |
2 ms |
20924 KB |
Output is correct - answer is '18' |
19 |
Correct |
2 ms |
20924 KB |
Output is correct - answer is '1176' |
20 |
Correct |
2 ms |
20924 KB |
Output is correct - answer is '1225' |
21 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '136' |
22 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '45' |
23 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '2500' |
24 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '380' |
25 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '2304' |
26 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '110' |
27 |
Correct |
2 ms |
20924 KB |
Output is correct - answer is '93' |
28 |
Correct |
2 ms |
20924 KB |
Output is correct - answer is '729' |
29 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '132' |
30 |
Correct |
4 ms |
20924 KB |
Output is correct - answer is '7' |
31 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '8' |
32 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '64' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
21060 KB |
Output is correct - answer is '124251' |
2 |
Correct |
0 ms |
21056 KB |
Output is correct - answer is '38226' |
3 |
Correct |
0 ms |
21056 KB |
Output is correct - answer is '249500' |
4 |
Correct |
0 ms |
21056 KB |
Output is correct - answer is '5778' |
5 |
Correct |
0 ms |
21056 KB |
Output is correct - answer is '247506' |
6 |
Correct |
3 ms |
21056 KB |
Output is correct - answer is '248004' |
7 |
Correct |
0 ms |
21064 KB |
Output is correct - answer is '973' |
8 |
Correct |
2 ms |
21060 KB |
Output is correct - answer is '123753' |
9 |
Correct |
4 ms |
21056 KB |
Output is correct - answer is '2346' |
10 |
Correct |
2 ms |
20924 KB |
Output is correct - answer is '53' |
11 |
Correct |
0 ms |
20924 KB |
Output is correct - answer is '52' |
12 |
Correct |
5 ms |
21068 KB |
Output is correct - answer is '976' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
23348 KB |
Output is correct - answer is '12497500' |
2 |
Correct |
58 ms |
23260 KB |
Output is correct - answer is '6481800' |
3 |
Correct |
162 ms |
23304 KB |
Output is correct - answer is '25000000' |
4 |
Correct |
115 ms |
23252 KB |
Output is correct - answer is '17816841' |
5 |
Correct |
15 ms |
23284 KB |
Output is correct - answer is '9945' |
6 |
Correct |
23 ms |
23240 KB |
Output is correct - answer is '504100' |
7 |
Correct |
27 ms |
23208 KB |
Output is correct - answer is '1512930' |
8 |
Correct |
3 ms |
21060 KB |
Output is correct - answer is '413' |
9 |
Correct |
4 ms |
21056 KB |
Output is correct - answer is '428' |
10 |
Incorrect |
7 ms |
21512 KB |
Output isn't correct - expected '7232', found '15360' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Halted |
0 ms |
0 KB |
- |