QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #277880 | #2592. 甲苯先生和大中锋的字符串 | SoyTony | 100 ✓ | 92ms | 27868kb | C++14 | 2.5kb | 2023-12-07 06:52:18 | 2023-12-07 06:52:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int t;
int n,k;
char s[maxn];
int siz[maxn];
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn<<1],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
struct SuffixAutomaton{
int tot,last;
int ch[maxn<<1][26];
int len[maxn<<1],link[maxn<<1],cnt[maxn<<1];
inline void init(){
for(int i=0;i<=tot;++i){
head[i]=0;
for(int c=0;c<26;++c) ch[i][c]=0;
}
tot=0,last=0;
link[0]=-1;
}
inline void extend(char c){
int cur=++tot;
len[cur]=len[last]+1,cnt[cur]=1;
int p=last;
while(p!=-1&&!ch[p][c]){
ch[p][c]=cur;
p=link[p];
}
if(p==-1) link[cur]=0;
else{
int q=ch[p][c];
if(len[p]+1==len[q]) link[cur]=q;
else{
int clone=++tot;
len[clone]=len[p]+1,link[clone]=link[q],cnt[clone]=0;
for(int i=0;i<26;++i) ch[clone][i]=ch[q][i];
while(p!=-1&&ch[p][c]==q){
ch[p][c]=clone;
p=link[p];
}
link[cur]=link[q]=clone;
}
}
last=cur;
}
inline void build(){
for(int i=1;i<=tot;++i){
add_edge(link[i],i);
}
}
void dfs(int u){
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
dfs(v);
cnt[u]+=cnt[v];
}
}
inline void solve(){
build();
dfs(0);
for(int i=1;i<=tot;++i){
if(cnt[i]==k){
++siz[len[link[i]]+1],--siz[len[i]+1];
}
}
for(int i=1;i<=n;++i) siz[i]+=siz[i-1];
int mx=0,ans=-1;
for(int i=n;i>=1;--i){
if(siz[i]>mx) mx=siz[i],ans=i;
}
printf("%d\n",ans);
}
}SAM;
int main(){
scanf("%d",&t);
for(int T=1;T<=t;++T){
scanf("%s",s+1);
n=strlen(s+1);
scanf("%d",&k);
cnt=0;
SAM.init();
for(int i=1;i<=n;++i) siz[i]=0;
for(int i=1;i<=n;++i) SAM.extend(s[i]-'a');
SAM.solve();
// if(t==21&&T>3) break;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 8020kb
input:
10 zdlzzlzllz 4 zyyykkyyyy 3 gssgsslsds 4 lyoyyyyhhh 4 cjjcjjjcjc 2 fiigfirfrf 4 dudzudzzud 3 vmgvxvvvmg 4 cceeeceeec 2 uupuppuuup 2
output:
1 3 -1 -1 3 1 1 -1 3 3
result:
ok 10 lines
Test #2:
score: 5
Accepted
time: 1ms
memory: 8016kb
input:
10 kykkykkkky 3 mpamzzmpap 4 gwlnlglnll 4 tvgvttggvv 3 mmgmgzazaa 4 lpllpppmlm 3 yyieyyieee 3 rkkkrkkkrr 2 ooovoovvoo 2 eoedoeeded 3
output:
2 -1 -1 1 -1 -1 -1 3 3 2
result:
ok 10 lines
Test #3:
score: 5
Accepted
time: 0ms
memory: 8008kb
input:
10 zvzzzdvvvv 3 momommmomm 2 ppppmpmppp 3 vdlvllvddv 3 xjujxjxuxx 3 vsejjjveev 4 rrrvrereve 3 hhfhyhyfhy 4 yyvvvvybbb 3 igttggttgi 3
output:
2 4 3 1 1 -1 1 -1 1 -1
result:
ok 10 lines
Test #4:
score: 5
Accepted
time: 1ms
memory: 10068kb
input:
10 vvuuvuevue 3 kaaakktkka 3 bbbbbbbbbb 3 vnvvvnvvvv 2 ddfdfdfddd 2 vvzzvczcvc 3 bteettvtev 4 faffaaffaf 3 xekktxxktk 4 sssesekksk 4
output:
2 -1 8 4 4 1 1 2 1 -1
result:
ok 10 lines
Test #5:
score: 5
Accepted
time: 20ms
memory: 25364kb
input:
21 cbaabbacbabbaaacbbcabbabcabbcbabacacabbccaaaaaaccccbbacabbccabababbbccbcabcbacbccababacbabaaabcaaaccbbbcacbabcbbacccbcabcaccbbacaacccabcacacbcbcbbccbababacacaaaacccaaababbcaccbabcccacababbabccbbcbccaaababbaacaaccacbcccbabbccccbacaabbbcacaacaccccaccabaccacaccaacabaaabcbbccccbbbbbbabccbbacabacabbac...
output:
-1 93 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997 6997
result:
ok 21 lines
Test #6:
score: 5
Accepted
time: 59ms
memory: 25156kb
input:
44 kdgoajrkqmaiiagpgqfplfbgifcbinfaqkmrrlhpghdmfkhmgmhrpgdglghablaqbnpqeclkjodmekgkdlkqpnehrkhrbhpaakqfmjnbdqlijqakjiihcnobdbqcincjdaonhjmkggqnepfldnqfgkfhldjcpljqjdmokefqkdjmqogciehmpkcgolildpjkqbhjgkfonpjkjnmrprmkkmrgdfpgbeprgcgkmkgfhnpoghochgkpahbdloimadjefoopgbanmqjrddbihjfhrgjkapcbajfdfaalraelo...
output:
58 106 97 2500 -1 95 48 9261 -1 84 -1 58 20 3915 103 26 92 10843 95 2 81 -1 2944 83 -1 96 -1 -1 -1 -1 -1 -1 7 3 2 3 1 5 5 2 6 7 3 3
result:
ok 44 lines
Test #7:
score: 5
Accepted
time: 63ms
memory: 24232kb
input:
33 kcufklrpmdqeiomibkrxvmsjbmspkuduwxsjklqogbsppwxqjihgvspogjvqganuphfrkohrprigqxpbiohvipdhqbxwbeljdqcogkxndxmtwtuwjulklprdqisjnfsinvwmxnrcmfolacbconmrevnuvhvceqljfbnephwdmegnhihvvlhbiunvdkaxslapmoltnkxrgvwffftsqclqwaordoinrifvoqrdsivbflgdrrnjtbcrrikuwschthebxvvkvkdtvbwotlaoesawcckavmxitdjlrgnoqqbor...
output:
41 81 -1 13523 91 42 11676 110 -1 -1 1245 110 -1 22444 -1 104 65 90 -1 35 -1 49 101 103 -1 93 2 106 2 93 1 5 2
result:
ok 33 lines
Test #8:
score: 5
Accepted
time: 68ms
memory: 25172kb
input:
36 ceaeddccecadcdaaddeaedeababcacccbcebcdddaebdedacbacddcdceeeedbecaadcdecaaedeebddbcbbbbdbcacabdecadbdceeeaedeadedaaacdaaaacbcdabdaeeedadaedccdbaeecdcdddacbeadabbcacaabdbbadcdbbeaecdecbbdaedbaedacacaaddceabcdaceeddbecbebccbdcdcaacaaddeabdbdbadbebcbadecbaaaadaacdacbcdececabcbceaaeeedcbdcbdabbdedbdda...
output:
-1 -1 56 105 83 2077 1332 33 1086 7388 104 2382 43 -1 109 -1 68 109 97 -1 -1 -1 83 -1 97 -1 3 103 2 9 4 2 3 93 86 3
result:
ok 36 lines
Test #9:
score: 5
Accepted
time: 68ms
memory: 27344kb
input:
57 ecfjgcfafegamjneajgnbilmidknlgfngjgmlmkacdabkldihhigcfekibhefldlgkhdgebihnhbkkjbediehmmnlddcafngnfhfjilahfbcnkdbmldfinefdgidjfiiknnfiifnlgbjbdknamcileamkgaflinihknnfdlchmlgbgfachglmgkgmkkiehcjenhhaehiadaaheajjegflamhkgbmnbibnngndafbbebiinbdefhngdeajenifficeachmfinjifdhefjimimnnmiblagcihghjlfmedim...
output:
100 102 105 100 -1 -1 -1 72 2490 14650 86 103 892 106 20 7704 -1 9212 33 95 94 92 -1 95 -1 107 2 -1 -1 -1 -1 -1 -1 -1 -1 2 2 5 8 1 3 5 4 1 2 2 4 3 3 5 2 1 3 4 7 2 1
result:
ok 57 lines
Test #10:
score: 5
Accepted
time: 92ms
memory: 24232kb
input:
31 bdbacacddabdbabaaccbcbbcbbddbaccdddbabadbbccbddcbbdacacdbbccbabaaababbddcbbdaabbcabaadabacabdbbdbcdcdcbbddbddcabdccdbcbcabddcbcddbbdddaccbbbacddabcbddddaddcabbdddcccdbaacbaaadabccabbacadaaacadbccdbddcbaccbcccaadbcddccadccdcdbacddbbabdccbbbbbadddccbcbdaabdbbbaacbbabdccadacddbcbddaadaaaaccbccaadabd...
output:
-1 62 86 94 -1 1005 1401 103 98 4074 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 31 lines
Test #11:
score: 5
Accepted
time: 67ms
memory: 25788kb
input:
70 fbecabecdeeaffffceecabccdbcddebbffdfaffccecfbfcedbeccaeefebacdbcacffcfbcbbbcaeecfcefaaddedcaedcceabefcaabfacbdeefaeeaffeafecdffffadcbbaceecabaefaabaaaceabbbeaebabdfabaefcebbbebbfafdcedbdcddeebdfbdafcebedcfbcfaaedcafcdffaeeabbbdaedefbfcfececcadebceeaefcafbbecfcfbffafeebaedacabceacadceacecedcefbbdf...
output:
-1 -1 14 90 5452 85 200 99 23 -1 51 -1 20 82 47862 14149 84 -1 61 1 -1 -1 -1 65 -1 83 -1 100 -1 -1 -1 -1 -1 108 -1 105 85 -1 3 1 3 3 4 2 2 4 2 2 4 1 4 4 4 3 3 5 3 2 1 6 6 3 3 4 2 7 8 2 1 2
result:
ok 70 lines
Test #12:
score: 5
Accepted
time: 53ms
memory: 24460kb
input:
23 abbaabacdbaabadadcaacadbaabcaababcabdadcbacdacddaddddcaacbccbdccbcdacddadbdddcdabcdbbdbdadcccaaddadbdcbcaabdcadadcbabcdcbbadcacbabcdaabaaddddddcbacdccbddbcbbaccbbbbbdbbcbabadabdcababaaccbacacabdbccddaaacadcbdacabdbbcdccccacdddbccbccbacacaddcaabbbdadbccbabbaddcabbbcdbadbdbbddcaccaabcbbdcbcbacdbdba...
output:
-1 -1 106 -1 5710 20 92 107 86 105 87 493 2078 18923 88 2204 103 82 94 89 102 88 91
result:
ok 23 lines
Test #13:
score: 5
Accepted
time: 59ms
memory: 27868kb
input:
23 kmhmojkibddnmikcbdqqlcanfedhpnjhfqcrfkifnjairjirkgndglrjqaonnfbabdafngigpgmnpcmggfjkqgcoeokrajqbmoefcmjprekoecclhkdgodabamhmojkibddnojkibddnmikjkibddnmikckmhmojkibddhmojkibddnmibddnmikcbdddnmikcbdqqbddnmikcbdqkibddnmikcbmojkibddnmidnmikcbdqqlojkibddnmikbddnmikcbdqibddnmikcbdmhmojkibddnjkibddnmikc...
output:
13 -1 84 109 -1 10360 -1 95 106 17 87 104 639 85 5030 32291 86 169 84 82 88 107 85
result:
ok 23 lines
Test #14:
score: 5
Accepted
time: 54ms
memory: 25516kb
input:
28 abaaaabbbabaaaaaaaaabbabbabbbabbbbbbaabbbabbabaabababbaabbaaabbbbbbbbaaaabaaaabaaaabbaaaaabababababbabbaabbbbabbabbbabbabaaabbbaaabaabbaaabaaabaaababaaabababaabaaaabbbbbabbbbbbbabbabbbbabaaaabaabbbaaababababaaababbaabbaababbaaabbbbabaaaabaabababbaaaaaabbbbaabbbababbabaaababbbabaabaaaaaaaabbbbabab...
output:
-1 89 -1 -1 -1 85 82 -1 -1 97 96 237 9138 -1 1436 803 2 21279 64 99 84 83 83 86 53 96 106 73
result:
ok 28 lines
Test #15:
score: 5
Accepted
time: 57ms
memory: 26036kb
input:
68 abacacabcddddbbbacaabdcabbddbcdbdaddcdaacdacabdadaaadcaadddbbccbccaabbbaabcbcbbbbcbaabaabdbccddababdbcdbdbcbcacacdacabcbadacdddadadacccbdaccaaccdcbdddbadbccabcabcadacaadccdcacbcdbccccbdaddccddaadacdabccbacdcbcddabbcabbdddddddcabbadddaabdccbbbbccdcabbdaacadaabcaabdabbdddaabbcdbadccdccbccccdaddbcdd...
output:
-1 20 10343 70 92 81 -1 101 100 47 60 4071 109 -1 1117 5856 29 -1 103 34 87 -1 -1 105 93 81 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 3 3 5 2 12 2 1 2 7 2 2 2 2 10 8 1 7 6 3 3 4 4 2 3 2 5 2 6 2 2
result:
ok 68 lines
Test #16:
score: 5
Accepted
time: 68ms
memory: 27568kb
input:
27 cbfabfafefeeebeefebfdcbeadeebdcdeccffaceaeaeffcddbceecccdbafedaadadcbfefdfdbedcbcceaeadcbbfdcddfeaafdecbbfafacfcedbbbcbddeaebcbfcbceeeffbddbdacfddecffdadcedeaaefdcdffbfceedeadfbbbefffcbbddfebffcaebbbcfefbeaaecacfdfbcbdfabafaaeccfecdcbeeadacddbacacddfccdfcedfadbaabbefbfebcbaabfadaffddeffacddddbccd...
output:
-1 109 15458 55 -1 -1 -1 14874 3 485 86 -1 -1 6898 16784 88 14 99 65 81 102 102 82 97 87 86 90
result:
ok 27 lines
Test #17:
score: 5
Accepted
time: 59ms
memory: 27540kb
input:
32 izfwqpzzndvibmphtpzlwexzqomnrdrbcyztnaucfrlheaozppknvhmmxzzoesrjqqedrygwrtdvtuuklgyhpktmlucsptbfkhldhtzymfuhbqrmxrtmeobpjdjyxmfjtqmallzzsvitlaiktbzxqapbdyzclelgxxhkjimdduzquhbqkancccdfdeioltukrduclghqbgjxnmnaodcqfgxikfyxbvhuycymkfelonldzadndgflodtakuylpfhphfbsngfbvsevtkkyqsjevfefbctqiahrijlxrtamn...
output:
82 -1 3218 -1 -1 -1 40 781 -1 -1 -1 95 94 4103 91 11357 14 93 -1 102 90 40 61 83 106 3 94 83 19 5 3 4
result:
ok 32 lines
Test #18:
score: 5
Accepted
time: 63ms
memory: 25920kb
input:
68 qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
6173 776 102 102 99 -1 -1 17066 86 -1 45 -1 10364 -1 157 -1 -1 87 83 -1 68 -1 -1 -1 -1 -1 -1 -1 96 -1 53 96 58 91 -1 96 106 2 3 4 2 3 2 2 4 2 2 5 2 7 2 4 3 1 3 2 2 5 3 7 3 4 4 3 5 7 2 2
result:
ok 68 lines
Test #19:
score: 5
Accepted
time: 57ms
memory: 25252kb
input:
43 xosrglbjgzftubzudkqkfpcscxuwvvjujclrpnavohqijpeobuzgmdbobvlyswsbafvssxnhferqvwexsffejgvkegkyecafhxxcumlzserocwnvdsbmbwyfekdjmfqwcnazblyupsksoxptpsgqrgxxrdifkydpndopqoligvcwstqjlycegbczgkfrjiiyownemaotvqrpjhbxhddogfnnsugdfobtkrzwrorngjessfpcksqrafgsamxhayamrbkjrcyyncqhkhjwbbndhvxjhuqhvsvmtgvlkvlxa...
output:
91 45 2974 86 22 89 -1 91 46 106 106 679 -1 5304 197 12730 98 -1 -1 104 -1 92 97 102 -1 -1 103 -1 -1 -1 1 3 1 2 2 2 2 7 2 2 1 6 7
result:
ok 43 lines
Test #20:
score: 5
Accepted
time: 60ms
memory: 24768kb
input:
26 cbgijncoipdkmedpnfeplfhbpgkelbenckflhhkagnkdbncochonmfolljpgkddnojifacfhppkanmppdnnacllnelepohmmaecbhhighcheogdcdacfmncaigpholdoafphnhnejeiiklknmmcijficlijjdmidchkppidimlahgkecghkamdchllbohjcjamipelibgiindmpjdkjpnlhigigobihbfabjljkcbcpepoocihcfdjnjbehcmpdbpelknfmpildhkbjcjlimefffjnhgmlhlpcfnicman...
output:
101 55 -1 45704 92 -1 71 -1 -1 -1 98 74 3161 -1 96 106 1121 101 100 3515 494 102 107 81 93 102
result:
ok 26 lines