QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#587674#801. 回文自动机lanhuo0 27ms410156kbC++172.6kb2024-09-24 21:03:052024-09-24 21:03:05

Judging History

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

  • [2024-09-24 21:03:05]
  • 评测
  • 测评结果:0
  • 用时:27ms
  • 内存:410156kb
  • [2024-09-24 21:03:05]
  • 提交

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
*/

Details

Tip: Click on the bar to expand more detailed information

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%