#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=3e5+5;
string s;
struct Node {
int nxt[26];
int len;
int sufflink;
int cnt;
vector<int>edges;
};
Node tree[maxn];
int suff;
int sz;
void addLetter(int pos){
int let = s[pos] - 'a';
int curr = suff;
while(1){
if(pos - tree[curr].len - 1 >= 0 and s[pos - tree[curr].len - 1] == s[pos]) break;
curr = tree[curr].sufflink;
}
if(tree[curr].nxt[let]){
suff = tree[curr].nxt[let];
tree[suff].cnt++;
return;
}
suff = ++sz;
tree[curr].nxt[let] = suff;
tree[suff].len = tree[curr].len + 2;
tree[suff].cnt = 1;
if(tree[suff].len == 1){
tree[suff].sufflink = 2;
tree[2].edges.push_back(suff);
return;
}
while(1){
curr = tree[curr].sufflink;
if(pos - tree[curr].len - 1 >= 0 and s[pos - tree[curr].len - 1] == s[pos]){
tree[suff].sufflink = tree[curr].nxt[let];
tree[tree[suff].sufflink].edges.push_back(suff);
break;
}
}
}
void init(){
sz = 2;
suff = 2;
tree[1].len = -1;
tree[1].sufflink = 1;
tree[2].len = 0;
tree[2].sufflink = 1;
tree[1].edges.push_back(2);
}
int ans;
void dfs(int nd){
for(auto i : tree[nd].edges){
dfs(i);
tree[nd].cnt += tree[i].cnt;
}
ans = max(ans, tree[nd].cnt * tree[nd].len);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int len = (int)s.size();
init();
for(int i = 0;i < len;i++){
addLetter(i);
}
dfs(1);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |