제출 #313178

#제출 시각아이디문제언어결과실행 시간메모리
313178vipghn2003회문 (APIO14_palindrome)C++14
100 / 100
108 ms108928 KiB
#include <bits/stdc++.h> using namespace std; const int N=3e5+5; struct Node { int nxt[26],sufflink; int len,cnt; vector<int>edges; } tree[N*2]; string s; int suff, num; long long ans=0; void add_letter(int pos) { int curr=suff; int curr_len=0; int letter=s[pos]-'a'; while(true) { curr_len=tree[curr].len; if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos]) break; curr=tree[curr].sufflink; } if(tree[curr].nxt[letter]) { suff=tree[curr].nxt[letter]; tree[suff].cnt++; return; } suff=++num; tree[num].len=tree[curr].len+2; tree[num].cnt=1; tree[curr].nxt[letter]=num; if(tree[num].len==1) { tree[num].sufflink=2; tree[2].edges.push_back(num); return; } while(true) { curr=tree[curr].sufflink; curr_len=tree[curr].len; if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos]) { tree[num].sufflink=tree[curr].nxt[letter]; tree[tree[curr].nxt[letter]].edges.push_back(num); break; } } } void init() { num=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); } void dfs(int node=1) { for(auto&i:tree[node].edges) { dfs(i); tree[node].cnt+=tree[i].cnt; } ans=max(ans,1ll*tree[node].len*tree[node].cnt); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> s; init(); for(int i=0;i<s.size();i++) add_letter(i); dfs(); cout<<ans; }

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<s.size();i++) add_letter(i);
      |                 ~^~~~~~~~~
#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...