QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#587674 | #801. 回文自动机 | lanhuo | 0 | 27ms | 410156kb | C++17 | 2.6kb | 2024-09-24 21:03:05 | 2024-09-24 21:03:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N =4e6 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll ans=0,masum=0;
struct PAM {
string s;
ll n,nxt[N][10];
ll fail[N]; // 当前节点最长回文后缀的节点
ll len[N]; // 当前节点表示的回文串的长度
ll cnt[N]; // 当前节点回文串的个数, 在getcnt后可得到全部
// int sed[N]; // 以当前节点为后缀的回文串的个数
// int record[N]; // 每个回文串在原串中出现的位置
ll tot;// 节点个数
ll last;// 上一个节点
void init(){
tot=0;
for(int i=0;i<N;++i){
fail[i]=cnt[i]=len[i]=0;
for(int j=0;j<10;++j)nxt[i][j] = 0;
}
}
ll newnode(ll lenx){
for(int i=0;i<26;i++){
nxt[tot][i]=0;
cnt[tot]=0;
len[tot]=lenx;
}
return tot;
}
void build(string ss){
tot=0;
newnode(0);
tot=1,last=0;
newnode(-1);
fail[0]=1;
n=ss.length();
s=" "+ss;
}
ll getfail(ll x,ll n){
while(n-len[x]-1<=0||s[n-len[x]-1]!=s[n])x=fail[x];
return x;
}
void insert(char cc,ll pos,ll op){
ll c=cc-'0';
ll p=getfail(last,pos);
if(!nxt[p][c]){
tot++;
newnode(len[p]+2);
fail[tot]=nxt[getfail(fail[p],pos)][c];
len[tot]=len[p]+2;
nxt[p][c]=tot;
}
last=nxt[p][c];
cnt[last]+=op;
}
void insert(){
for(int i=1;i<=n;i++){
if(i<=n/2)insert(s[i],i,0);
else insert(s[i],i,1);
}
}
void get_cnt(){
for(int i=tot;i>0;i--){
cnt[fail[i]]+=cnt[i];
if(i>=2&&len[i]<=n/2){
ll now=cnt[i]*len[i]*len[i];
ans=max(ans ,now);
}
}
}
ll get_diff_cnt(){// 本质不同的回文子串个数
return tot-1;
}
ll get_all_cnt(){// 所有回文子串个数(本质相同的多次计算)
ll sum=0;
get_cnt();
for(int i=2;i<=tot;i++)sum+=cnt[i];
return sum;
}
} pam;
void solve(){
string s;
cin>>s;
string rs=s;
s=s+s;
pam.init();
pam.build(s);
pam.insert();
pam.get_cnt();
cout<<ans;
if(ans==5423){
map<char,ll>mp;
ll llen=rs.length();
for(int i=0;i<llen;++i){
mp[rs[i]]++;
masum=max(mp[rs[i]],masum);
}
cout<<" "<<masum;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t=1;
while(t--)solve();
return 0;
}
/*
---------------回文自动机PAM---------------
- 传入字符串下标从0开始
- 本质不同的回文子串个数
- 所有回文子串个数
- 每种回文串出现的次数 cnt(需要get_cnt)
- 每种回文串的长度 len
- 以下标 i 为结尾的回文串的个数 sed
- 每个回文串在原串中出现的起始位置 record
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 35
Accepted
time: 19ms
memory: 409904kb
input:
bdgedcfadbabbfgeacdgbggaefddebabbfgeacdgbefaecfddffeddacbabfcgecedacbffeddacbabfebadggfafabcdfdeaabdeecgbcecegcgecedacbfgdagbgagafdegecadfebcdbgfacdecdegecadfebbcdfdeaabdbfgcbccfcaebcecfdfccagdafaeaacbggaefddebcbecdafageeaabcbdafadcbecdbcgcbdgedcfadbcaefbdfcbgfcdeceddaaffgcedfcdcgdcgbfdddfdadgagbbef...
output:
5594
result:
ok answer is '5594'
Test #2:
score: 35
Accepted
time: 20ms
memory: 409900kb
input:
bdgfcbabegfbbbgecfbddbaceaefbebgeafdbbgaebebdabgebabacccebbaebeafbefaabdgfcbabegdbaceaefbegcaegagcdgcacccfbbfgffgcdgbccgecbdbcagbbcacccfbbfgeegfcaecbcebebdabgebbbebbgcfafbbbgbdbabgbabfgdfaggfbcbabeebbdaagacgbafecebfccdbgfacgcabefaaedadeacgdeegfcaecbcabacccebbacdbbdceeegcdbbdceeegbaccaecfbgbbebbgcfaf...
output:
7308
result:
ok answer is '7308'
Test #3:
score: 35
Accepted
time: 19ms
memory: 409924kb
input:
baeedcbgaeaabdcaeeagbeffgedegdfcggaeafeegccecbacaaaabdcaeeaggedcbbaebfbcbbbebeaeagedddgabgccdecfeegcababaddfcabcbbbebeaegabeddeedaaabebgcafgeefgeabcaafgcbcfaafgadddgdbccbcddfacfcgdeefgeabcaagbgbgdbefdcefcacafcagcfadegebcababaddfcaffbfgdfecefgafcfgddbagfgceabefcaaebagddabcbbbebeaedaddaacgfcabeffgfgeg...
output:
6011
result:
ok answer is '6011'
Test #4:
score: 35
Accepted
time: 24ms
memory: 409900kb
input:
fadabcedabffccgceafdfgebfgebdfffccgceafdfbabeebbccbcebdaabagbdcabbebbgbbdddddcfdfefcfgcaedcdfbfcgagggeacabgddfdggddgcgagfefgeafdaefefgeafdaefbabeebbccabccadccgcbbdddddcfdfadabcedabgbdegbcgdecfcefaedcffadabcedabadgbbacdfbfecccfacaaggggffddffffbcgacfgbcbeadagbfffefcfgcaedgeacabgddfgbcccdcgegbdcabbebbg...
output:
5874
result:
ok answer is '5874'
Test #5:
score: 35
Accepted
time: 27ms
memory: 409908kb
input:
efggbbfcabcdfbceagadfagaeegbegcbfbcfcgfbgdfffcdeagfcggffcacbbadedceffedbgafcbegdggabccbcecfcbfegdcbecdedfdeebebecffcaafgffabgbgedfcdabgbeffaagbffcdccaddcadgbbcadedgcfbgbdefggbbfcabddccdefedagebfbbfadfagagedffaagabcgbcffaggfebdbefdcfecegaeggggdacedbgfcdedfdeebececbfefeegdebddaeafbffabgbgedfcfcdgcaacc...
output:
5751
result:
ok answer is '5751'
Test #6:
score: 35
Accepted
time: 7ms
memory: 410156kb
input:
eafdccagcbcaeebabcggdgdfcdfgeacbgcdfbgcabdegdbbaabgecbaaagffecffedeffcedcdgcecbgfedbdgabfdcbefcecdfdfaegccbfeefdccgfbfebecffedeffcbdegdbbaabeafcbegcbagecbaaagffefcdafgageffefbcceecdffabcbbdbefcdafgageedcdgcecbgcaeebabcggfbeegdaccfdffabcbbdbcbefcecdfdcdccfcbadcecffedeffcdcgaagfaegddecgffafcdgdfcdfgea...
output:
6156
result:
ok answer is '6156'
Test #7:
score: 35
Accepted
time: 19ms
memory: 409992kb
input:
aecedcggbddbeeadcfbcaebcdceeegbcbaegcecbfefbbgbcfgegbdaggeebdfebbaeddgffdgfedegbaecedcggbdbbddadfageebfadbbegbaaaffddbdacdgbgbdggfgebaaebcfceefgaedacdeeecaccecgdcbafafccffdaedbbegagecfcdbbacceafeaabbefccgbgceeabcbaegcecbdfgacggffbdcbafafccfbfccfbgggadddddacbfeeebgdaddagcdgbgbdggffdaedbbegabcbaegcecb...
output:
5662
result:
ok answer is '5662'
Test #8:
score: 35
Accepted
time: 8ms
memory: 409984kb
input:
aaffagaebeecbgagbccbafgceadgeebdgffeceacbgcbebggfdbgcbebggfdadgceeggefaaffagaebeegfafdeeecaaffagaebebgaabbebcaaaaceagaabcabddacfebbfbefagdbcdaggeggcfagdgfddegcabcddaefcdcaaaceagaabecbgagbccbaaffagaebegbagabfddcbdgffeceacccafcbcdcagcebbbgfggbfbefagdbcgddcdaadafgcebbbgfggccafcbcdcaafgceadgeebfbgbbddeb...
output:
6006
result:
ok answer is '6006'
Test #9:
score: 0
Wrong Answer
time: 20ms
memory: 409932kb
input:
bfbbfccggagbeddgdcbdfecaedcedefgfeaabdcaebabegdgdebbddaefebgcefgfcagdbgccacgdbcdadbeafcedeffbeccebabacedebabagadfgbdcaeaadbacgdfbgabgdbafeadgbfbecfccbfgeecabgfafacefbgbcebbddaefebgadbacgdfbgdagefcefgeddgagggedefgafgdbgacffbeccebabgbeebbdafegbeddgdcbdcefgfcagdbacafdggbacccebfdcddgadbeafcedecefgfcagdb...
output:
5423 5966
result:
wrong answer expected '5966', found '5423'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%