제출 #262094

#제출 시각아이디문제언어결과실행 시간메모리
262094mohamedsobhi777Palindromes (APIO14_palindrome)C++14
100 / 100
96 ms41076 KiB
//#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...