QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125882 | #801. 回文自动机 | NOI_AK_ME# | 0 | 6ms | 17228kb | C++23 | 1.6kb | 2023-07-17 20:48:21 | 2023-07-17 20:48:23 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define dub long double
const int MAXN = 2e6+7;
const int inf = 1e9+7;
const dub eps = 1e-14;
using namespace std;
int tr[MAXN][30], len[MAXN], fail[MAXN];
int lst = 1, cnt = 1;
string s;
queue <int> q;
int in[MAXN], f[MAXN];
inline int read( )<%
int x = 0 ; short w = 0 ; char ch = 0;
while( !isdigit(ch) ) { w|=ch=='-';ch=getchar();}
while( isdigit(ch) ) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w ? -x : x;
%>
int get(char x){ return x - 'a'; }
void insert(int x){
int p = lst, np = ++cnt, q, nq; lst = np;
len[np] = len[p] + 1; f[np] = 1;
for(; p and !tr[p][x]; p = fail[p]) tr[p][x] = np;
if(!p) fail[np] = 1;
else if(len[q = tr[p][x]] == len[p] + 1) fail[np] = q;
else{
nq = ++cnt;
fail[nq] = fail[q];
len[nq] = len[p] + 1;
fail[q] = fail[np] = nq;
memcpy(tr[nq], tr[q], sizeof(tr[q]));
for(;p and tr[p][x] == q; p = fail[p]) tr[p][x] = nq;
}
}
void tpsort( ){
for(int i = 1; i <= cnt; i++)
in[fail[i]]++;
for(int i = 1; i <= cnt; i++)
if(!in[i]) q.push(i);
while(!q.empty()){
int x = q.front( ); q.pop( );
f[fail[x]] += f[x];
in[fail[x]]--;
if(!in[fail[x]]) q.push(fail[x]);
}
}
int main( )<%
cin >> s;
for(int i = 0; i < (int)s.size( ); i++)
insert(get(s[i]));
tpsort();
ll ans = 0;
for(int i = 2; i <= cnt; i++)
if(f[i] > 1) ans = max(ans, (ll)f[i] * len[i]);
cout << ans;
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: 6ms
memory: 16712kb
input:
bdgedcfadbabbfgeacdgbggaefddebabbfgeacdgbefaecfddffeddacbabfcgecedacbffeddacbabfebadggfafabcdfdeaabdeecgbcecegcgecedacbfgdagbgagafdegecadfebcdbgfacdecdegecadfebbcdfdeaabdbfgcbccfcaebcecfdfccagdafaeaacbggaefddebcbecdafageeaabcbdafadcbecdbcgcbdgedcfadbcaefbdfcbgfcdeceddaaffgcedfcdcgdcgbfdddfdadgagbbef...
output:
5594
result:
ok answer is '5594'
Test #2:
score: 0
Accepted
time: 1ms
memory: 17228kb
input:
bdgfcbabegfbbbgecfbddbaceaefbebgeafdbbgaebebdabgebabacccebbaebeafbefaabdgfcbabegdbaceaefbegcaegagcdgcacccfbbfgffgcdgbccgecbdbcagbbcacccfbbfgeegfcaecbcebebdabgebbbebbgcfafbbbgbdbabgbabfgdfaggfbcbabeebbdaagacgbafecebfccdbgfacgcabefaaedadeacgdeegfcaecbcabacccebbacdbbdceeegcdbbdceeegbaccaecfbgbbebbgcfaf...
output:
7308
result:
ok answer is '7308'
Test #3:
score: 0
Accepted
time: 2ms
memory: 16564kb
input:
baeedcbgaeaabdcaeeagbeffgedegdfcggaeafeegccecbacaaaabdcaeeaggedcbbaebfbcbbbebeaeagedddgabgccdecfeegcababaddfcabcbbbebeaegabeddeedaaabebgcafgeefgeabcaafgcbcfaafgadddgdbccbcddfacfcgdeefgeabcaagbgbgdbefdcefcacafcagcfadegebcababaddfcaffbfgdfecefgafcfgddbagfgceabefcaaebagddabcbbbebeaedaddaacgfcabeffgfgeg...
output:
6011
result:
ok answer is '6011'
Test #4:
score: 0
Accepted
time: 5ms
memory: 14840kb
input:
fadabcedabffccgceafdfgebfgebdfffccgceafdfbabeebbccbcebdaabagbdcabbebbgbbdddddcfdfefcfgcaedcdfbfcgagggeacabgddfdggddgcgagfefgeafdaefefgeafdaefbabeebbccabccadccgcbbdddddcfdfadabcedabgbdegbcgdecfcefaedcffadabcedabadgbbacdfbfecccfacaaggggffddffffbcgacfgbcbeadagbfffefcfgcaedgeacabgddfgbcccdcgegbdcabbebbg...
output:
5874
result:
ok answer is '5874'
Test #5:
score: 0
Accepted
time: 3ms
memory: 15328kb
input:
efggbbfcabcdfbceagadfagaeegbegcbfbcfcgfbgdfffcdeagfcggffcacbbadedceffedbgafcbegdggabccbcecfcbfegdcbecdedfdeebebecffcaafgffabgbgedfcdabgbeffaagbffcdccaddcadgbbcadedgcfbgbdefggbbfcabddccdefedagebfbbfadfagagedffaagabcgbcffaggfebdbefdcfecegaeggggdacedbgfcdedfdeebececbfefeegdebddaeafbffabgbgedfcfcdgcaacc...
output:
5751
result:
ok answer is '5751'
Test #6:
score: -35
Wrong Answer
time: 1ms
memory: 17208kb
input:
eafdccagcbcaeebabcggdgdfcdfgeacbgcdfbgcabdegdbbaabgecbaaagffecffedeffcedcdgcecbgfedbdgabfdcbefcecdfdfaegccbfeefdccgfbfebecffedeffcbdegdbbaabeafcbegcbagecbaaagffefcdafgageffefbcceecdffabcbbdbefcdafgageedcdgcecbgcaeebabcggfbeegdaccfdffabcbbdbcbefcecdfdcdccfcbadcecffedeffcdcgaagfaegddecgffafcdgdfcdfgea...
output:
5755
result:
wrong answer expected '6156', found '5755'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%