QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587548#801. 回文自动机lanhuo0 11ms105492kbC++173.1kb2024-09-24 20:36:032024-09-24 20:36:05

Judging History

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

  • [2024-09-24 20:36:05]
  • 评测
  • 测评结果:0
  • 用时:11ms
  • 内存:105492kb
  • [2024-09-24 20:36:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define double long double
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

long long ans = 0;
/*
---------------回文自动机PAM---------------

- 传入字符串下标从0开始
- 本质不同的回文子串个数
- 所有回文子串个数
- 每种回文串出现的次数 cnt(需要get_cnt)
- 每种回文串的长度 len
- 以下标 i 为结尾的回文串的个数 sed
- 每个回文串在原串中出现的起始位置 record
*/

struct PAM {
	string s;
	long long n;
	long long nxt[N][10];
	long long fail[N]; // 当前节点最长回文后缀的节点
	long long len[N]; // 当前节点表示的回文串的长度
	long long cnt[N]; // 当前节点回文串的个数, 在getcnt后可得到全部
	// int sed[N]; // 以当前节点为后缀的回文串的个数
	// int record[N]; // 每个回文串在原串中出现的位置
	long long tot; // 节点个数
	long long 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;
		}
	}
	int newnode(int 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;
	}
	int getfail(int x, int n)
	{
		while (n - len[x] - 1 <= 0 || s[n - len[x] - 1] != s[n])
			x = fail[x];
		return x;
	}
	void insert(char cc, int pos, int op)
	{
		int c = cc - '0';
		int 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;
			// sed[tot] = sed[fail[tot]] + 1;
			nxt[p][c] = tot;
		}
		last = nxt[p][c];
		cnt[last] += op;
		// record[last] = pos;
	}
	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)
			{
				long long now=cnt[i]*len[i]*len[i];
				ans = max(ans ,now);
			}
		}
	}
	int get_diff_cnt() // 本质不同的回文子串个数
	{
		return tot - 1;
	}
	int get_all_cnt() // 所有回文子串个数(本质相同的多次计算)
	{
		int 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<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t=1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 35
Accepted
time: 11ms
memory: 105452kb

input:

bdgedcfadbabbfgeacdgbggaefddebabbfgeacdgbefaecfddffeddacbabfcgecedacbffeddacbabfebadggfafabcdfdeaabdeecgbcecegcgecedacbfgdagbgagafdegecadfebcdbgfacdecdegecadfebbcdfdeaabdbfgcbccfcaebcecfdfccagdafaeaacbggaefddebcbecdafageeaabcbdafadcbecdbcgcbdgedcfadbcaefbdfcbgfcdeceddaaffgcedfcdcgdcgbfdddfdadgagbbef...

output:

5594

result:

ok answer is '5594'

Test #2:

score: 35
Accepted
time: 7ms
memory: 105280kb

input:

bdgfcbabegfbbbgecfbddbaceaefbebgeafdbbgaebebdabgebabacccebbaebeafbefaabdgfcbabegdbaceaefbegcaegagcdgcacccfbbfgffgcdgbccgecbdbcagbbcacccfbbfgeegfcaecbcebebdabgebbbebbgcfafbbbgbdbabgbabfgdfaggfbcbabeebbdaagacgbafecebfccdbgfacgcabefaaedadeacgdeegfcaecbcabacccebbacdbbdceeegcdbbdceeegbaccaecfbgbbebbgcfaf...

output:

7308

result:

ok answer is '7308'

Test #3:

score: 35
Accepted
time: 4ms
memory: 105276kb

input:

baeedcbgaeaabdcaeeagbeffgedegdfcggaeafeegccecbacaaaabdcaeeaggedcbbaebfbcbbbebeaeagedddgabgccdecfeegcababaddfcabcbbbebeaegabeddeedaaabebgcafgeefgeabcaafgcbcfaafgadddgdbccbcddfacfcgdeefgeabcaagbgbgdbefdcefcacafcagcfadegebcababaddfcaffbfgdfecefgafcfgddbagfgceabefcaaebagddabcbbbebeaedaddaacgfcabeffgfgeg...

output:

6011

result:

ok answer is '6011'

Test #4:

score: 35
Accepted
time: 7ms
memory: 105412kb

input:

fadabcedabffccgceafdfgebfgebdfffccgceafdfbabeebbccbcebdaabagbdcabbebbgbbdddddcfdfefcfgcaedcdfbfcgagggeacabgddfdggddgcgagfefgeafdaefefgeafdaefbabeebbccabccadccgcbbdddddcfdfadabcedabgbdegbcgdecfcefaedcffadabcedabadgbbacdfbfecccfacaaggggffddffffbcgacfgbcbeadagbfffefcfgcaedgeacabgddfgbcccdcgegbdcabbebbg...

output:

5874

result:

ok answer is '5874'

Test #5:

score: 35
Accepted
time: 6ms
memory: 105492kb

input:

efggbbfcabcdfbceagadfagaeegbegcbfbcfcgfbgdfffcdeagfcggffcacbbadedceffedbgafcbegdggabccbcecfcbfegdcbecdedfdeebebecffcaafgffabgbgedfcdabgbeffaagbffcdccaddcadgbbcadedgcfbgbdefggbbfcabddccdefedagebfbbfadfagagedffaagabcgbcffaggfebdbefdcfecegaeggggdacedbgfcdedfdeebececbfefeegdebddaeafbffabgbgedfcfcdgcaacc...

output:

5751

result:

ok answer is '5751'

Test #6:

score: 35
Accepted
time: 4ms
memory: 105272kb

input:

eafdccagcbcaeebabcggdgdfcdfgeacbgcdfbgcabdegdbbaabgecbaaagffecffedeffcedcdgcecbgfedbdgabfdcbefcecdfdfaegccbfeefdccgfbfebecffedeffcbdegdbbaabeafcbegcbagecbaaagffefcdafgageffefbcceecdffabcbbdbefcdafgageedcdgcecbgcaeebabcggfbeegdaccfdffabcbbdbcbefcecdfdcdccfcbadcecffedeffcdcgaagfaegddecgffafcdgdfcdfgea...

output:

6156

result:

ok answer is '6156'

Test #7:

score: 35
Accepted
time: 8ms
memory: 105488kb

input:

aecedcggbddbeeadcfbcaebcdceeegbcbaegcecbfefbbgbcfgegbdaggeebdfebbaeddgffdgfedegbaecedcggbdbbddadfageebfadbbegbaaaffddbdacdgbgbdggfgebaaebcfceefgaedacdeeecaccecgdcbafafccffdaedbbegagecfcdbbacceafeaabbefccgbgceeabcbaegcecbdfgacggffbdcbafafccfbfccfbgggadddddacbfeeebgdaddagcdgbgbdggffdaedbbegabcbaegcecb...

output:

5662

result:

ok answer is '5662'

Test #8:

score: 35
Accepted
time: 4ms
memory: 105476kb

input:

aaffagaebeecbgagbccbafgceadgeebdgffeceacbgcbebggfdbgcbebggfdadgceeggefaaffagaebeegfafdeeecaaffagaebebgaabbebcaaaaceagaabcabddacfebbfbefagdbcdaggeggcfagdgfddegcabcddaefcdcaaaceagaabecbgagbccbaaffagaebegbagabfddcbdgffeceacccafcbcdcagcebbbgfggbfbefagdbcgddcdaadafgcebbbgfggccafcbcdcaafgceadgeebfbgbbddeb...

output:

6006

result:

ok answer is '6006'

Test #9:

score: 0
Wrong Answer
time: 3ms
memory: 105260kb

input:

bfbbfccggagbeddgdcbdfecaedcedefgfeaabdcaebabegdgdebbddaefebgcefgfcagdbgccacgdbcdadbeafcedeffbeccebabacedebabagadfgbdcaeaadbacgdfbgabgdbafeadgbfbecfccbfgeecabgfafacefbgbcebbddaefebgadbacgdfbgdagefcefgeddgagggedefgafgdbgacffbeccebabgbeebbdafegbeddgdcbdcefgfcagdbacafdggbacccebfdcddgadbeafcedecefgfcagdb...

output:

5423

result:

wrong answer expected '5966', found '5423'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%