# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
440220 | keta_tsimakuridze | 회문 (APIO14_palindrome) | C++14 | 107 ms | 90156 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
int t,in[N],idx,suff;
vector<int>V[N];
string s;
queue<int> q;
struct st{
int vis[27];
int sufflink;
int cnt;
int len;
} tree[N];
void add(int i){
int cur = suff;
while(true) {
if(s[i - tree[cur].len - 1] == s[i]) {
if(tree[cur].vis[s[i]-'a']) {
suff = tree[cur].vis[s[i]-'a'];
tree[suff].cnt++;
return;
}
suff = ++idx;
tree[idx].cnt = 1;
tree[cur].vis[s[i]-'a'] = idx;
tree[idx].len = tree[cur].len + 2;
break;
}
cur = tree[cur].sufflink;
}
if(tree[idx].len == 1){
tree[idx].sufflink = 2;
return;
}
while(true) {
cur = tree[cur].sufflink;
if(s[i - tree[cur].len - 1] == s[i]) {
tree[idx].sufflink = tree[cur].vis[s[i]-'a'];
V[idx].push_back(tree[cur].vis[s[i]-'a']);
in[tree[cur].vis[s[i]-'a']]++;
break;
}
}
}
main(){
cin>>s;
int n = s.size();
s = '#' + s;
idx = 2;
tree[1].len = -1;
tree[2].len = 0;
in[1] +=2;
tree[1].sufflink = tree[2].sufflink = 1;
suff = 2;
for(int i=1;i<=n;i++){
add(i);
}
for(int i=1;i<=idx;i++) {
if(!in[i]) q.push(i);
}
int ans = 0;
while(q.size()){
int u = q.front();
q.pop();
ans = max(ans, tree[u].len * tree[u].cnt);
for(int i=0;i<V[u].size();i++) {
in[V[u][i]]--;
tree[V[u][i]].cnt += tree[u].cnt;
if(!in[V[u][i]]) q.push(V[u][i]);
}
}
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... |