QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587616#801. 回文自动机lanhuo0 15ms409972kbC++172.4kb2024-09-24 20:51:302024-09-24 20:51:31

Judging History

你现在查看的是最新测评结果

  • [2024-09-24 20:51:31]
  • 评测
  • 测评结果:0
  • 用时:15ms
  • 内存:409972kb
  • [2024-09-24 20:51:30]
  • 提交

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%