QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#820184 | #275. Palindromes | Mirasycle | 0 | 2ms | 9812kb | C++14 | 845b | 2024-12-18 20:02:48 | 2024-12-18 20:02:50 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
struct PAM{
int len[maxn],fa[maxn],ch[maxn][27];
int cnt[maxn],tot,lst,n; char s[maxn];
void init(char *S){
tot=lst=1; int n=strlen(S+1);
len[0]=0; len[1]=-1; fa[0]=1;
for(int i=1;i<=n;i++) s[i]=S[i];
}
void add(int c,int pos){
int p=lst;
while(s[pos]!=s[pos-len[p]-1]) p=fa[p];
//if(!ch[p][c]){
int np=++tot,q=fa[p]; len[np]=len[p]+2;
while(s[pos]!=s[pos-len[q]-1]) q=fa[q];
fa[np]=ch[q][c]; ch[p][c]=np;
//}
lst=ch[p][c]; cnt[lst]++;
}
}p;
int n,cnt[maxn]; char s[maxn]; ll ans;
int main(){
cin>>(s+1); int n=strlen(s+1); p.init(s);
for(int i=1;i<=n;i++) p.add(s[i]-'a'+1,i);
for(int i=p.tot;i>=1;i--) p.cnt[p.fa[i]]+=p.cnt[i],ans=max(ans,1ll*p.cnt[i]*p.len[i]);
cout<<ans;
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 8
Accepted
time: 0ms
memory: 9772kb
input:
abacaba
output:
7
result:
ok single line: '7'
Test #2:
score: 8
Accepted
time: 1ms
memory: 7640kb
input:
www
output:
4
result:
ok single line: '4'
Test #3:
score: 8
Accepted
time: 1ms
memory: 7700kb
input:
abacababa
output:
9
result:
ok single line: '9'
Test #4:
score: 8
Accepted
time: 1ms
memory: 7708kb
input:
r
output:
1
result:
ok single line: '1'
Test #5:
score: 8
Accepted
time: 0ms
memory: 7768kb
input:
xd
output:
1
result:
ok single line: '1'
Test #6:
score: 8
Accepted
time: 0ms
memory: 7632kb
input:
dd
output:
2
result:
ok single line: '2'
Test #7:
score: 8
Accepted
time: 1ms
memory: 7776kb
input:
opo
output:
3
result:
ok single line: '3'
Test #8:
score: 8
Accepted
time: 1ms
memory: 7704kb
input:
opoo
output:
3
result:
ok single line: '3'
Test #9:
score: 8
Accepted
time: 1ms
memory: 7704kb
input:
abacabadabacaba
output:
15
result:
ok single line: '15'
Test #10:
score: 8
Accepted
time: 2ms
memory: 9812kb
input:
xxxxxyxxxxyxxxxx
output:
24
result:
ok single line: '24'
Test #11:
score: 8
Accepted
time: 0ms
memory: 7700kb
input:
xxxyxxxyzzzabcdxxdcba
output:
10
result:
ok single line: '10'
Test #12:
score: 8
Accepted
time: 1ms
memory: 7624kb
input:
qpppppppwowpppppq
output:
24
result:
ok single line: '24'
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 7700kb
input:
mqmwmemrmtymmmmmmmmqwertyeeeeeeeee
output:
9
result:
wrong answer 1st lines differ - expected: '25', found: '9'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%