# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1150640 | SmuggingSpun | Palindromes (APIO14_palindrome) | C++20 | 0 ms | 324 KiB |
#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
string s;
ll ans = 0;
struct Node{
int link, len, cnt, child[26];
Node(){
memset(this->child, -1, sizeof(this->child));
this->cnt = 0;
}
};
vector<Node>eer(2);
void dfs(int s){
for(int i = 0; i < 26; i++){
if(eer[s].child[i] != -1){
dfs(eer[s].child[i]);
}
}
eer[eer[s].link].cnt += eer[s].cnt;
maximize(ans, 1LL * eer[s].cnt * eer[s].len);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
eer[eer[1].len = eer[0].link = eer[1].link = 0].len = -1;
cin >> s;
for(int i = 0, root = 0; i < s.size(); i++){
s[i] -= 97;
while(i - eer[root].len < 1 || s[i] != s[i - eer[root].len - 1]){
root = eer[root].link;
}
if(eer[root].child[s[i]] == -1){
int cur = eer[root].child[s[i]] = eer.size();
eer.emplace_back(Node());
if((eer[cur].len = eer[root].len + 2) > 1){
int r = root;
while(true){
if(i - eer[r = eer[r].link].len > 0 && s[i - eer[r].len - 1] == s[i]){
eer[cur].link = eer[r].child[s[i]];
break;
}
}
}
else{
eer[cur].link = 0;
}
}
eer[root = eer[root].child[s[i]]].cnt++;
}
dfs(0);
dfs(1);
cout << ans;
}
Compilation message (stderr)
# | 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... |