# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
31178 | tatatan | 회문 (APIO14_palindrome) | C++11 | 19 ms | 37912 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int N=3e5+5;
int suff[N],len[N],lz[N],nxt[N][26],cur,tt=3;
LL ans;
string s;
stack<int> st;
void add(int x) {
while(s[x-len[cur]-1]!=s[x])
cur=suff[cur];
int y=s[x]-'a';
if(nxt[cur][y]) {
cur=nxt[cur][y];
++lz[cur];
return;
}
int nw=tt++;
st.push(nw);
++lz[nw];
len[nw]=len[cur]+2;
if(len[nw]==1) {
suff[nw]=2;
nxt[cur][y]=nw;
cur=nw;
return;
}
int tmp2=cur;
cur=suff[cur];
while(s[x-len[cur]-1]!=s[x])
cur=suff[cur];
suff[nw]=nxt[cur][y];
cur=nw;
nxt[tmp2][y]=cur;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>s;
len[1]=-1; suff[1]=1;
len[2]=0; suff[2]=1;
cur=1;
for(int i=0;i<s.size();++i)
add(i);
while(!st.empty()) {
int x=st.top();
st.pop();
ans=max(ans,1LL*len[x]*lz[x]);
lz[suff[x]]+=lz[x];
}
cout<<ans<<endl;
}
컴파일 시 표준 에러 (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... |