QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698265#3844. LCS Spanning Treeyzj123AC ✓1190ms804304kbC++203.4kb2024-11-01 18:28:082024-11-01 18:28:08

Judging History

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

  • [2024-11-01 18:28:08]
  • 评测
  • 测评结果:AC
  • 用时:1190ms
  • 内存:804304kb
  • [2024-11-01 18:28:08]
  • 提交

answer

#include <bits/stdc++.h>
#define Re register int
#define LL long long
using namespace std;
const int MAXN=4e6+5;
int n;
char ch[MAXN];
struct Suffix_Automaton{
    int O,link[MAXN],maxlen[MAXN],trans[MAXN][26];
    //link[i]: 后缀链接
    //trans[i]: 状态转移数组
    Suffix_Automaton(){O=1;}//根初始化为1
    inline int insert(Re ch,Re last)
    {
        if(trans[last][ch]){
            Re p=last,x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])return x;//即最初的特判1
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=y;
                return y;//即最初的特判2
            }
        }
        Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            Re x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
}SAM;
vector<int> g[MAXN], col[MAXN];
int prt[MAXN];
pair<int, int> a[MAXN];
int get_prt(int x) {
    if (x == prt[x]) return x;
    return prt[x] = get_prt(prt[x]);
}
int cr[MAXN];
int ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) prt[i] = i;
    for(Re i=1;i<=n;++i){
        scanf("%s",ch+1);
        Re last=1;
        for(Re j=1;ch[j];++j)
        {
            last=SAM.insert(ch[j]-'a',last);
            col[last].push_back(i);
        }
    }
    // for (int i = 1; i <= SAM.O; i++)
    // {
    //     cout << "u:" << i << " ";
    //     cout << "col:";
    //     for (int x : col[i]) cout << x << " ";
    //     cout << "\n";
    // }
    for (int i = 1; i <= SAM.O; i++) g[SAM.link[i]].push_back(i);
    // for (int i = 1; i <= SAM.O; i++) 
    // {
    //     cout << "u:" << i << " ";
    //     cout << "v:";
    //     for (int x : g[i]) cout << x << " ";
    //     cout << "\n";
    // }

    for (int i = 1; i <= SAM.O; i++) a[i] = make_pair(SAM.maxlen[i], i);
    sort(a + 1, a + SAM.O + 1, [](pair<int, int> A, pair<int, int> B){
        return A.first > B.first;
    });
    vector<int> vex;
    int k = 0;
    for (int i = 1; i <= SAM.O; i++) 
    {
        vex.clear();
        int u = a[i].second, val = a[i].first;
        // cout << "u:" << u << " " << val << "\n";
        for (int x : col[u]) vex.push_back(x);
        for (int x : g[u]) vex.push_back(cr[x]);
        for (int j = 1; j < vex.size(); j++)
        {
            int x = vex[j], y = vex[j - 1];
            int prtx = get_prt(x), prty = get_prt(y);
            // cout << prtx << " " << prty << "\n";
            if (prtx != prty) 
            {
                prt[prtx] = prty;
                ans += val;
                k++;
                // cout << "---------------val:" << val << "\n";
            }
        }
        if (vex.size() > 0) cr[u] = get_prt(vex[0]);
    }
    // cout << "k:" << k << "\n";
    cout << ans;
    return 0;
}
/*
4
icpc
macau
regional 
contest

3
ababa 
babab 
aba
*/

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 12200kb

input:

4
icpc
macau
regional
contest

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 4ms
memory: 11856kb

input:

3
ababa
babab
aba

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 288ms
memory: 469928kb

input:

26
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 4ms
memory: 11848kb

input:

7
jia
ran
jin
tian
chi
shen
me

output:

9

result:

ok single line: '9'

Test #5:

score: 0
Accepted
time: 4ms
memory: 12016kb

input:

10
theysaynothinglastsforever
weareonlyheretoday
loveisnowornever
bringmefaraway
takemetoyourheart
takemetoyoursoul
givemeyourhandandholdme
showmewhatloveis
bemyguidingstar
itiseasytakemetoyourheart

output:

55

result:

ok single line: '55'

Test #6:

score: 0
Accepted
time: 7ms
memory: 14240kb

input:

100
dblkekaekijliimalcaidjjfaghdmhifkiebieffbddjmflkhagajcfmkccjjadgiijdbdldgbbhgcfdcadbeiabkemiefdccmhdcfilhkfabmfdmigfgigdcibgaeicedfiidgecbhdamiaiefbmbgbjhklbhafmhckklbmmiemkcbfgjihmdjkai
bciiecmbc
cdjailkkbefkbmlekiefdhklcbdccfbgkagflfemjjmkjmcgiibldlmhbcldjajgafmakfbhecgcckkkglklljhmliehidbkicm...

output:

476

result:

ok single line: '476'

Test #7:

score: 0
Accepted
time: 870ms
memory: 578968kb

input:

2000
ecbhcebgbcjgjiihdefajfbbaajfjdedggciaegdiijhijgedbgejhgjjfhabdfhbihdeegcehbcjhgebcjachbdeiefejefhcjdihfcfgeegdahhjhjiiffjjadifiijjbhhjjeffabiaagcjhaachjbiecfeceefddecjchjfibgedfdghgdijdcdahfeddjihbhbbghjjffdcibaggiiadbaajhfcgdbaafbicahjhabfdbeacccfdehebciafaaffdfjdciafbhidbahdccjhjdadcciecfbhac...

output:

17765

result:

ok single line: '17765'

Test #8:

score: 0
Accepted
time: 894ms
memory: 553992kb

input:

1413
gjjmlceglbmbibjmmfcfmickcllfekgmicmifdbfgdgbeecgjgalbfkdfljjkclfgkaacdgigblaiaiehkeiccbjamikdgcjfemhhfebicddelklibjafmjhleebkimeblljfembgcgacdlkhjmbijjgacjaajebjfkcllffalheefeaedbmmkicaeecckdmedddbikeieimjmmcfdcgamicfbeimkjfamidjfhejdgiehkjkbdaaaeieldfibkkcgallieiamfehcdggiigkabblgigjgdlmflmafj...

output:

11429

result:

ok single line: '11429'

Test #9:

score: 0
Accepted
time: 69ms
memory: 28676kb

input:

2000000
j
o
v
p
h
b
t
s
x
y
u
c
t
n
p
l
b
e
c
v
d
c
p
s
u
m
d
d
i
m
h
t
a
e
j
i
i
c
c
h
d
x
j
w
m
a
j
p
f
l
n
i
q
c
c
k
q
g
q
b
u
z
u
v
d
d
f
n
i
j
v
n
i
e
l
w
h
v
m
m
i
z
w
y
d
z
l
w
h
b
x
b
a
r
y
d
x
f
r
h
p
o
u
x
u
f
u
b
c
i
p
l
j
o
j
o
n
u
k
w
x
h
z
x
z
y
d
y
d
w
h
u
k
b
u
e
i
o
g
n
y
x
y
h
l
j
...

output:

1999974

result:

ok single line: '1999974'

Test #10:

score: 0
Accepted
time: 735ms
memory: 534144kb

input:

2
adwkgmoosmodblpylbpymmnbzyjzddfegdqppefjstpueeurhjpuvdxudgtgmaksfdjwhogcivwmbqeiavcxybubknkwqwqxzaujoclyzhnaztibonzpotsaicwaznyapujfwugvdtxfmhgcuhrlcklnminnxnoojzvfwbczubgijnldwcqzocodmdqltgzcguicwmdsombxbmcxotyfvmijsaulhtnppxtnkygakhzltbjjwjqrwyaozwzgroxhmquyocazjzkecvqzfgqdhttgpuojilqwbmurruscvd...

output:

8

result:

ok single line: '8'

Test #11:

score: 0
Accepted
time: 1190ms
memory: 793248kb

input:

1413
ababaaaababbababbabbaababaabaaaabaabbabababbbabbaaababbbbabbababaaababbbaabbaaabaaabababbbbbbbabbaababbababaaabaabbaaaaabbbaaabbabaaabaabaababaaabbabbabaabaabbaabbbbbbabbabaaaabbababaabbababbbaaabababaabaababaaaabaaaaababbbbbbbbabbabaabbaabbbbabbbbbaaabbbbbaabbbaabababababaaabbaaaaabbaaaabaaaaa...

output:

42405

result:

ok single line: '42405'

Test #12:

score: 0
Accepted
time: 29ms
memory: 23300kb

input:

1413
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1995156

result:

ok single line: '1995156'

Test #13:

score: 0
Accepted
time: 1032ms
memory: 803356kb

input:

1
baababbbbbaaabbaabbabaabbabaababaabaaabbbbbbbabbbababbbabaaababbbabbabaaabbbbbaabbaabbaabaaabaaaabbbabbbaaabbbbbabbbaaabaabbabbbbaabbbabbbababaaabaababaabbbababbabbbbaaabbaabbbbbbabbabaaaabaaaabbbaaabbbbbbaaabaaabbabbababbabaabbabababababbbbaaababaaaabaabaaababbbbbabbbaaaaaababbbbbababaabbbabaaaab...

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 753ms
memory: 589660kb

input:

1413
fnjfbnhskrerdxmxrlthhclkgcfrwukmccsfpbazsetxbfwvsseauqmcuutqofeshwxyxxasbtpfaocsgguayjcsdxitcnllliljglbjesqggubmbvozessjpcctrngdwsoedrpkjgsqatedrtfvlzhddjyvxfavxozcfooowhgzalctgjrriywmhvjeajzzxadepsslbbkdmpxsaoljmixvdgafpbgocjstdmegnrkbijvizjtnrqiwykdpmjfquxjympeziqdsbydahwpapyypkbfwmkohkxfwplv...

output:

464827

result:

ok single line: '464827'

Test #15:

score: 0
Accepted
time: 690ms
memory: 563956kb

input:

1413
vrotfwuoloxhchhuitgryunhjurviyookrumnoabeziigrdpmlglfvurrlmblapvtlkhbmkgmuosltjxerkkmfdfspgeqwbjhlslycrkwhehdohhhrtuwwbpmivegwppikaimtulbyugobnwvjsrhtivddzjcrbmbbupvoayoxefatdvexnmqxhwdjhfairbmlsjbvjrspwsibonydbrcinfrwkrfduropcrkljeahyijoxhryaujnzakmurpqkgfmxpxivzsuhbihkchnwsaxtmlpfbfphldgccrab...

output:

254582

result:

ok single line: '254582'

Test #16:

score: 0
Accepted
time: 615ms
memory: 741328kb

input:

1413
bbbbbabaabbabbbbbbaaabbaabaaabaabbabbaabaaabbbaaaaaabbaaabaaaabbabbbbbbbabbbbbabaaabaababbbaaabababbaaaaabbbbbabaaaabaaabbabbabbabaabaabaaabbbabbabaaababbbbbbaaaaababbabbbaabaaabaabbabbaaabaababaaabbbbabbabbabaaabbbabbbabbbbabaabbbabbbbabbbbaaabbbabaaabbaaaaabbababbababbbbbbaaaabaaaabaaaaabbabb...

output:

1498740

result:

ok single line: '1498740'

Test #17:

score: 0
Accepted
time: 483ms
memory: 509084kb

input:

1413
lcoqmejczgztniltuwtqgzmgyjdvkiqvlgozlzdmhchwksqerjuxkigjslgetycefqfqriezkmvwgndxyzvjiducocihbkogctyuecvqqqnxgsuerrpbwldkooupyixbdvxjzsaskppqhlvafmcbyfmmtgduqaxvxwfwohoawftfrofwahxyplmktpglrfjobolpxbsvhlaabhydrxeijqueibqzgzoipbzmctjlelnfsllllptufqaptqpzrdjgeluigdwlolsjzdwkusgcigrbzgcqlozpbvahzys...

output:

1285703

result:

ok single line: '1285703'

Test #18:

score: 0
Accepted
time: 686ms
memory: 552180kb

input:

500
eqrouzrzqavpwipjhbpbbsypakjkmpithzhdazdqzyivgzhpawsdorsrdcdstllansenrjgsjqqspxhrvaumtnfwrioktzmiusynbegluwdlvmcsoyghlleetuopwdzqxxdzdlmzjrkgdozunhbythfoetdaydswcxxgllfucsbhgcbtjduemztquysvdkrikqovbvpdnsmuwopitjmhkhyfiqaldtvnjjikhzpwubsqriymtnueuulcmnqrglepxobgqqcktvaldbzwovcirnneafvisczpsavisauo...

output:

93437

result:

ok single line: '93437'

Test #19:

score: 0
Accepted
time: 1006ms
memory: 798604kb

input:

500
aababbabbbabbbaabbaaababaabbabbaaaabbaaababababbbbbbbaabaaaabaabaabaababaabbaaabaaabaaaaabaababbaabaaabaaabababbabaabaaabaaaabaaabaabbabbbbababbbbbbabbbbbabaababbabaaaaaaabaabababbaabbbbbbbaaaaababaababaabbaaabaabbbaaaabbabbabbbbaabbbbaaaaabaabbabbababbaaababaaabbbabbabaaaabbaabbababbbbabbabbbaa...

output:

621482

result:

ok single line: '621482'

Test #20:

score: 0
Accepted
time: 547ms
memory: 530024kb

input:

500
xkhhkzemvoilwwysloxrngtnalowphqotywezcsuqahpwhjjwjalpvysipqxyhoshkyioqchqlyothxrqacivacersdqbrkkdisuywdqibgdidwbfylbanhsfmkjgutlemfeiiusjaxuftvltgoutxoajajpwfbatiedtawcavwhptsizieufsxpuigqnjqguwknwirydqgujadlljfqeehynopazfhtetgabazgqhbzjgkupsltwusjijmkqtduomvpmwvcfydoeoluiypesjqbscnjxqdleacsyzwd...

output:

1305055

result:

ok single line: '1305055'

Test #21:

score: 0
Accepted
time: 472ms
memory: 526716kb

input:

500
afdppltdvwipholvfwehnlbcmcxujuxlbabqnwtiudzbunzzjfiwqjzclyzwswiuylmmjiwdlygflfhumrtcbuhosgnmexieivsrdpuopcwckdywwrzxliofqdswacaixtbckxtzzpbjubgqthqgrgmhjgdjidtiyukitdhuukeqmmhhvzpmfbvqjazsfuceqomjuwdoijhwvodqptewwzmgznafhejxsvimtldcvkasagjpbnnzpbhoohtxnewgceuvrxzojahjgsajhniwoqlezgbnlzvndpixpkly...

output:

1248710

result:

ok single line: '1248710'

Test #22:

score: 0
Accepted
time: 716ms
memory: 589340kb

input:

4000
gdlglqbydbkucqucvkhjoicbrutfyulgywmlpqlurxpvqhkywpnnwerqgjnnxyheruhcotfjpohhyrfwiulgbcyjnnwlofrfcykqspchfjqfcyemupuvutghifuykmeokohcfjlmueuycykwpeujzctkhpibmfvorjdmqztnqyqzjgzcsekanoxzescqxxeojjczivoywhzhpzjhftkvjhunzwfzwlphvsifpweldfstgdcoymjktfzvdfubqlilfqrvpxiuednlgqzhekrypstuxpwqagbgzubotli...

output:

587656

result:

ok single line: '587656'

Test #23:

score: 0
Accepted
time: 687ms
memory: 702380kb

input:

4000
baabaabbababbbbbabaabaabababaabaabbbabbaaaabbbabbaaababbbaaaabaababbbbbbbbaaaaabbabaabbabbabaabbaaabbbaaaabbbbaabaabbbbaabbaaaaaaaaaaaaabbbaaaabaabbbabbaabaabaaaaaabbaaaaabaaaaabbbaaaaabaabaaaaaaabbaabbaaabbaabaabbabbbaaaaaaabbbabbbabbaaabaababbaaabbaabbababaabbbbaaaaabbaabbbaaabbabababbbbbaaaa...

output:

867646

result:

ok single line: '867646'

Test #24:

score: 0
Accepted
time: 734ms
memory: 704640kb

input:

4000
baaaabbabbaaaabbbaaabbababaaaababbbaaabbbbbbbaabaabbbbbbbbbbbabbaabaabbbaabaabbaaaababbbaaabbbabaababaababbaaaaabaabbbabbababbbbbaaaaaaabbabababbaabbaaaabbbbababbbbbbaaaababbbbbbaababbaabbaabbbababbaabbabbaaababababaaababbbaaabbaababbbbbaaaabababaabbabaabaaaaabbaaaabbababaaaaaaababaabbbbabbbabb...

output:

870160

result:

ok single line: '870160'

Test #25:

score: 0
Accepted
time: 469ms
memory: 511236kb

input:

4000
jnbnjwgrxbxyqkbxyktdciatkisupcgkaanotwsywpwnczkakgfmohiypavecbrddgrwemuadsphrchdioswvaxnastcvmhasbwynsbsmqafsjjcybzvbwidqchnqpnjqjjfdkzpbzuvldyjgzejxpmntuajlpufrlzkaisoonwikhonlrvvrqszrenfgtmyeokhwcxkrwtbdjqqalltddvvhicqbroifyrbcootmjwrsmhuxspdykahscxwtnganxepnskabgrvuzrutgxttxdlbajvqpvdmbtatfc...

output:

913862

result:

ok single line: '913862'

Test #26:

score: 0
Accepted
time: 38ms
memory: 25268kb

input:

4000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1979531

result:

ok single line: '1979531'

Test #27:

score: 0
Accepted
time: 551ms
memory: 547256kb

input:

4000
fdhdijdfcdeedcbjgafdgcdegdbibaahdhaeifbdafhfhaefacigedcdhfbifdhbcjhaeidhdccdchicbjafceabjdchgjaabhbffgcajhdbecghdiehffjgiddhcfhdcabhhfigcdjihffagaibhjhhcdegiecbedabaajdgjbefbdbadcdeefgbibbhgaedhbhjgejchfjiididfcibjefhfgebiagfdfejjgbhdcfefghdafgjbbijaeciebghgcgiijhedeijahecfabgcbhefacbbaijdghdhe...

output:

1228665

result:

ok single line: '1228665'

Test #28:

score: 0
Accepted
time: 514ms
memory: 518580kb

input:

4000
rjdknocpagvrnghrpyukwifkkddprokianvndxdwgczcauhwrkpqmhqsmxqpmoxhazmujpspurtwndsfphxcrnwfnmuzauictvwfmowghscvvwckgzoxnkcawybzukbohyvtmrcwjgrgdvzovoosphzmirifzwmbfzuauwkmgoaodbfasvtjcuxmnftmcfohhkhdgtppkrfnvmpnhiwletasztebbskidtnjocaywgnrsdecnapsvpkuloxojjymelxtpyrlgfcakiexkurglbcwscmblkpqvmjlmcw...

output:

911422

result:

ok single line: '911422'

Test #29:

score: 0
Accepted
time: 401ms
memory: 330648kb

input:

100000
tduxfndk
uneyosepeblysz
myyzqqfxlyol
hueyo
vxkovfhrybgmvlhweq
jkcclhdeyo
dyggb
mokfduurtqfsmaeynq
gluuajukjnjc
dfcjqnme
xyrupyxgfnwd
hvdjjbewg
jjeyjmmlyol
fiqebs
otpjpq
nfmezyyuyme
wxyiuymslehvl
coshvqaht
tftlwgbnjyicrvjmuwrx
owpmmwkqpvhwxhiujh
vxrvymrouzryawtwombk
ukkzjbon
gokkrpnzmhonmhkfpj...

output:

989636

result:

ok single line: '989636'

Test #30:

score: 0
Accepted
time: 381ms
memory: 319512kb

input:

100000
baaabbbbabbabaaaba
baabbaababbababbb
bbbbbaababab
baaabbaa
abbabbbb
baaabba
baaabbbbbab
bababbabbbb
aababbbbbaabbbbabbbb
abaababbaaaaabbb
abaaabaaabbbbabbb
bababaababbb
aababbabbbbbbababba
abaabbabab
abbabbaaabaaaabbaaba
abbaaabbaabbbba
bbaababbabbaaabaaaa
aaababaaabbbabb
babbbb
bbbbaaaabaabb...

output:

1282986

result:

ok single line: '1282986'

Test #31:

score: 0
Accepted
time: 336ms
memory: 278724kb

input:

100000
pkhvbtnxfvxaem
uxvbtnxcgcsmwurthw
rfvxaem
wgzfvxaem
fafvxaem
nghhlpjfdga
wcljhoesadwmfwhvbtnx
uvbtnx
bcbffvxaemvbtnx
jhoesadwmfwhvbtnx
ncgcsmwurthwvbtnx
kyvbtnxjhoesadwmfwh
wavbtnxjhoesadwmfwh
ivbtnxssu
qnghhlpjfdgarjw
vbtnxibjhoesadwmfwh
zfvxaemigqvbtnx
swcgcsmwurthwsc
sjhoesadwmfwh
dfvxaemp...

output:

1170625

result:

ok single line: '1170625'

Test #32:

score: 0
Accepted
time: 32ms
memory: 31200kb

input:

100000
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaa
aaaaa
aaaaa
aaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaaaa
aaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaa
aaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaa
...

output:

1950179

result:

ok single line: '1950179'

Test #33:

score: 0
Accepted
time: 575ms
memory: 566252kb

input:

20
cqhcbnnuobmgcqfdzbuvyajaidogyrtcjbemouifxulzlqcmtwiryttiwhpuykxjldvaxefuastnkvaeukxsdtdcauwbevkqziswmzrmrmabkchemhyrabtavqdajwzphqhuggbrujigzfhqxcrtcifvvvfgrevavfwdlauhjenkjudgyubcfhxcccivjfyemujywfhfjxsutvcsreuwnuypwimfqmlcjucfzklkhdeaahurnrqalqrjzfrrsctbzygaktltyrvyyqsnjinwyghzmyqgdmhekpeulrnjj...

output:

201946

result:

ok single line: '201946'

Test #34:

score: 0
Accepted
time: 765ms
memory: 801792kb

input:

20
baaababababababbaaaabababaaaabbabbaaabbbaabbaabaabbbabaabbbabbaabbbbabaaaabaabaabbbbaaaabbaaaaabaaaabaabbbbbbaaabbbabbaaaababbbbbbbaabbbababbabaababaaabbbbaabbaaaaababbbabaaaaabbaabababaabbbbabaaaaaababbabbbbabbabaaaabbaabaabaabaaaabbbbaaabbbbabbababbbabbbabaaaabbbaaaaabbbababbaaabbbbaabbbbbbabba...

output:

187803

result:

ok single line: '187803'

Test #35:

score: 0
Accepted
time: 492ms
memory: 532228kb

input:

20
wighspqotssudabkedkygymrryunfudbdlkxbdnwxfqbitnmwxmeyyypysfgoihtuuqxxgtullvvgjhcivigwiyucdatnkmhefgblbxymtusedwozhxxrvruaunngbxkifnvhkwvfqolvmawvxtnunjuhwjnzizioofvabqgtgtpvtnqshfmwoidmssmatwohblhdepwmjnhcbavkfjgwslikfumysdfwombscxfnnopqomcwyksqvaaaxoaprflgtmaxmfkbwcrkqtgodaeabgcyvepmjduervefcqgy...

output:

265680

result:

ok single line: '265680'

Test #36:

score: 0
Accepted
time: 58ms
memory: 65916kb

input:

20
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1799368

result:

ok single line: '1799368'

Test #37:

score: 0
Accepted
time: 1044ms
memory: 804304kb

input:

2
aabaaabababbaababaaabaaaaababaabaabaabaabbbbbbaabaaabaabaabaabbbbbbaaaabbbabaabbbabaaabbaabababbbbbbbbaaabbbbbaabaababaabbabaaabbbbaabaaaababaaaabbaaaaababbabbbaababaaaaaabaababaaaaaaaabbbaaaaaaaaaaaaaabaaaaaaaabaabbbaabbabbabbabbaabbaabbaababaaabbababbbbaaaababbbaababbaabbabbbabaababaabaababaaaab...

output:

92934

result:

ok single line: '92934'

Test #38:

score: 0
Accepted
time: 712ms
memory: 557212kb

input:

2
jcmgevxqwiaflstvldrnmkeoeczrruqbxfjdagtyptfcoyybepqqzvggxgxpcpsbubfxhyvyubbkbznfqdysyeywmxlrodslgxipyfougrgkstriwpavwatkzgbolwbrtjgtownxnthfoyqlqsimvbwuhakuwllrurllqakdwtlkrdvjvfvqiunruxlslwjhqwsgzcjvvwfpzdyxkwntqakmawglurskonqnpcknarecwezhaoasrmgrkmefgwpujijbmvqomwqjarsbguvxgcqrqwwwsnsexdhjazanvq...

output:

91737

result:

ok single line: '91737'

Test #39:

score: 0
Accepted
time: 138ms
memory: 454376kb

input:

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

93662

result:

ok single line: '93662'

Test #40:

score: 0
Accepted
time: 685ms
memory: 590568kb

input:

10
cdvthwmepkhrkkvpucesqgrdwtzdvicynxrutfykridcsbrpfvhwdabzucdpkhpxhgtcospfashuvajdxqzarcclefcrosqvakyoenughdadgmgdchgvjiinpleddvbfhzuloqtvvtabfihkpnfaxqqmburgrslathljxehvahwhsftjszkpradswxaqrlqlvewukdpmlouftnomoydfajzzgzpxnhkilhcykskxiecburpkrtsuctvktkhitsqhzuflopjwwnysgneaiwumqpwlbetwwldxfiiuatqwh...

output:

735652

result:

ok single line: '735652'

Test #41:

score: 0
Accepted
time: 663ms
memory: 561608kb

input:

4000
fcrfjdagkknhhvvklrmnnnqcrmjnifrphkwsnyaxiqfpnczytnngbejusuhabapjkodzmgwvydmlfomabzhedsywmhyohqzreeqqmpnkuawcoicrhlwndwjsehilzjfdnxwcmjmjjklzsptcbrpenaytjgfjpmmfjihyuvhfguhyjacktrrgrpadyhmptaueldcfzjkfdrfptizmbqvvixyiekxzmudxxgcwrpdxilmcvnqweltokrwqdtpsnvpndulujpttchxxvotzbppmilcmguewpvjupuoalku...

output:

555122

result:

ok single line: '555122'

Test #42:

score: 0
Accepted
time: 876ms
memory: 776684kb

input:

4000
abbaaabaabbabbbbaaaaaabaaaaaaababbabbaaabbaaabbabaaaababaabaaaabbbbbbbbaabaaaaaaaaaababbaababababababaabbabaabaababbaaaabaaaababaabbabbabaaaaaababaaababbabbbbabbbbaaaabaabaaaaabaabbaaaabbbbbbaaaaaaaaaabbabbabbaababbaababababbabbbbbbbaaababbbaabbbabaabbbbaabbbabaaabaaaaabbabbbbbabbbaaaaaaababbab...

output:

777185

result:

ok single line: '777185'

Test #43:

score: 0
Accepted
time: 1040ms
memory: 803804kb

input:

2
baaaaaaabaaabaaaaabbaababbabbababbabbaabaabbbbbbbbabbbabaaabaabbbbbbabaabbaaabbbabaaaabbababbaabbbabaaaabaabbaaabaaabbbbabaabbbbababbabaabbabbabbababaabbabbbaaabababaabbbbbabaabbaabaaabbbaababababbaabaaaabaabbbbabbaababbbbabbaaabbbbbbbabababbaaabbbbaaabbaababababaabbbbaaabaaabbbababbbbbababbbabbba...

output:

54

result:

ok single line: '54'