QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#587616 | #801. 回文自动机 | lanhuo | 0 | 15ms | 409972kb | C++17 | 2.4kb | 2024-09-24 20:51:30 | 2024-09-24 20:51:31 |
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;
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.size();
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);
}
}
cout<<tot<<endl;
}
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;
s=s+s;
pam.init();
pam.build(s);
pam.insert();
pam.get_cnt();
cout<<ans;
}
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: 0
Wrong Answer
time: 15ms
memory: 409972kb
input:
bdgedcfadbabbfgeacdgbggaefddebabbfgeacdgbefaecfddffeddacbabfcgecedacbffeddacbabfebadggfafabcdfdeaabdeecgbcecegcgecedacbfgdagbgagafdegecadfebcdbgfacdecdegecadfebbcdfdeaabdbfgcbccfcaebcecfdfccagdafaeaacbggaefddebcbecdafageeaabcbdafadcbecdbcgcbdgedcfadbcaefbdfcbgfcdeceddaaffgcedfcdcgdcgbfdddfdadgagbbef...
output:
219 5594
result:
wrong answer expected '5594', found '219'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%