이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
string s;
int num,suff;
struct node{
int next[26];
int len,num,sufflink;
}tree[N];
inline void ini(){
num = suff = 2;
tree[1].len = -1;tree[1].sufflink = 1;
tree[2].len = 0;tree[2].sufflink = 1;
}
inline void add(int pos){
int cur = suff, curlen = 0;
int let = s[pos]-'a';
while (true){
curlen = tree[cur].len;
if (pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos])
break;
cur = tree[cur].sufflink;
}
if (tree[cur].next[let]){
suff = tree[cur].next[let];
tree[tree[cur].next[let]].num++;
return;
}
suff = ++num;
tree[cur].next[let] = num;
tree[num].len = tree[cur].len+2;
tree[tree[cur].next[let]].num++;
if (tree[num].len == 1){
tree[num].sufflink = 2;
return;
}
while(true){
cur = tree[cur].sufflink;
curlen = tree[cur].len;
if (pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos]){
tree[num].sufflink = tree[cur].next[let];
break;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>s;int n = s.size();
ini();
for(int i=0;i<n;++i)
add(i);
for(int i=n+3;~i;--i)
tree[tree[i].sufflink].num += tree[i].num;
long long ans = 0;
for(int i=3;i<n+3;i++)
ans = max(ans, 1LL*tree[i].num*tree[i].len);
cout<<ans;
}
# | 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... |