이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "elephants.h"
#include<bits/stdc++.h>
#define I inline void
using namespace std ;
using ld = long double ;
using ll = long long ;
const int N = 3e5 + 7 , mod = 1e9 + 7 ;
int n;
ll ans ;
string s;
int num , suf ;
struct node{
int nxt[26] ;
int len ;
int num ;
int occ ;
int lazy ;
int suflnk ;
} tree[N] ;
bool addL(int pos){
int cur = suf , curlen = 0 ;
int let = s[pos] - 'a' ;
while(1){
curlen = tree[cur].len ;
if(pos - 1 - curlen >=0 && s[pos - 1 - curlen ] == s[pos])
break ;
cur = tree[cur].suflnk ;
}
if(tree[cur].nxt[let]){
suf = tree[cur].nxt[let] ;
tree[suf].lazy++ ;
return 0 ;
}
num ++ ;
suf = num ;
tree[num].len = tree[cur].len + 2 ;
tree[cur].nxt[let] = num ;
tree[num].lazy ++ ;
if(tree[num].len == 1){
tree[num].suflnk = 2 ;
tree[num].lazy = 1;
return 1 ;
}
while(1){
cur = tree[cur].suflnk ;
curlen = tree[cur].len ;
if(pos -1 - curlen >= 0 && s[pos] == s[pos - 1 - curlen ]){
tree[num].suflnk = tree[cur].nxt[let] ;
break ;
}
}
tree[num].num = 1 + tree[tree[num].suflnk].num ;
return 1 ;
}
I init(){
suf = num = 2 ;
tree[1].len = -1 ;
tree[2].len = 0 ;
tree[1].suflnk = 1 ;
tree[2].suflnk = 1 ;
}
int pal[N] ;
int vis[N] ;
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
init() ;
cin >> s ;
n = (int) s.size() ;
for(int i = 0 ;i < n ;i++){
addL(i) ;
}
priority_queue<int> q ;
for(int i = 3 ;i <=num ;i++){
q.push(i) ;
}
while(q.size()){
int ret = q.top() ; q.pop() ;
if(vis[ret]++)continue ;
pal[ret] = tree[ret].lazy ;
if(tree[ret].suflnk > 2){
tree[tree[ret].suflnk].lazy+=tree[ret].lazy ;
q.push(tree[ret].suflnk) ;
}
}
for(int i = 3 ;i <= num ;i++){
ans = max(ans , 1ll * tree[i].len * pal[i] ) ;
}
cout<< ans << endl;
return 0 ;
}
# | 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... |