QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#587548 | #801. 回文自动机 | lanhuo | 0 | 11ms | 105492kb | C++17 | 3.1kb | 2024-09-24 20:36:03 | 2024-09-24 20:36:05 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%