QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#854878#8668. 回文路径cyrxdzj100 ✓537ms58764kbC++148.2kb2025-01-12 10:30:512025-01-12 10:30:51

Judging History

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

  • [2025-01-12 10:30:51]
  • 评测
  • 测评结果:100
  • 用时:537ms
  • 内存:58764kb
  • [2025-01-12 10:30:51]
  • 提交

answer

// Author: cyrxdzj
// Problem: 
// 			A.
// 			回文路径		
// Contest: undefined - 
// 					PKUSC 2024 Day 1				
// URL: https://qoj.ac/contest/1659/problem/8668
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
using namespace std;
//#define debug
const int MAXN=3e5;
const int MODCNT=2;
const long long BASE[MODCNT]={29,31},MOD[MODCNT]={998244353,19260817};
int n;
char s[2][MAXN+5];
int ans;
struct Seg
{
    int l,r;
    int mid,offset;
    int len()
    {
        if(l==0)
        {
            return 0;
        }
        return r-l+1;
    }
};
bool operator<(Seg a,Seg b)
{
    if(a.l==b.l)
    {
        return a.r<b.r;
    }
    return a.l<b.l;
}
vector<Seg>seg_by_l[MAXN+5],seg_by_r[MAXN+5];
int corner_pt;
long long qpow_cache[2][MAXN*2+5],inv_cache[2][MAXN*2+5];
long long qpow(long long a,long long b,int id)
{
    long long res=1;
    while(b)
    {
        if(b&1)
        {
            res=res*a%MOD[id];
        }
        a=a*a%MOD[id];
        b>>=1;
    }
    return res;
}
struct Hash
{
    int len;
    long long data1[MODCNT],data2[MODCNT];
    Hash()
    {
        len=0;
        for(int i=0;i<MODCNT;i++)
        {
            data1[i]=data2[i]=0;
        }
    }
    Hash(char c)
    {
        len=1;
        for(int i=0;i<MODCNT;i++)
        {
            data1[i]=data2[i]=c-'a'+1;
        }
    }
    bool check()
    {
        for(int i=0;i<MODCNT;i++)
        {
            if(data1[i]!=data2[i])
            {
                return false;
            }
        }
        return true;
    }
    void prt()
    {
        printf("%d",len);
        for(int i=0;i<MODCNT;i++)
        {
            printf(" %9lld",data1[i]);
        }
        for(int i=0;i<MODCNT;i++)
        {
            printf("  %9lld",data2[i]);
        }
        printf("\n");
    }
}pfx[2][MAXN+5];
Hash operator +(Hash a,Hash b)
{
    Hash res;
    res.len=a.len+b.len;
    for(int i=0;i<MODCNT;i++)
    {
        res.data1[i]=((a.data1[i]*qpow_cache[i][b.len]%MOD[i])+b.data1[i])%MOD[i];
        res.data2[i]=(a.data2[i]+(b.data2[i]*qpow_cache[i][a.len]%MOD[i]))%MOD[i];
    }
    return res;
}
Hash operator -(Hash a,Hash b)
{
    Hash res;
    res.len=a.len-b.len;
    for(int i=0;i<MODCNT;i++)
    {
        res.data1[i]=(a.data1[i]-(b.data1[i]*qpow_cache[i][a.len-b.len]%MOD[i])+2*MOD[i])%MOD[i];
        res.data2[i]=(a.data2[i]-b.data2[i]+2*MOD[i])%MOD[i]*inv_cache[i][b.len]%MOD[i];
    }
    return res;
}
Hash get_hash(int l,int r)
{
    if(l==1)
    {
        if(r<=corner_pt)
        {
            return pfx[0][r];
        }
        else
        {
            return pfx[0][corner_pt]+(pfx[1][r-1]-pfx[1][corner_pt-1]);
        }
    }
    return get_hash(1,r)-get_hash(1,l-1);
}
Seg get_reverse(int i,int offset)
{
    Seg res=(Seg){0,0,0,0};
    int extra=0;
    int left=1,right=min(i,n+1-(i+offset)+1);
    while(left<=right)
    {
        int mid=(left+right)>>1;
        Hash tmp=get_hash(i-mid+1,i+offset+mid-1);
        if(tmp.check())
        {
            extra=mid;
            left=mid+1;
        }
        else
        {
            right=mid-1;
        }
    }
    if(extra)
    {
        res=(Seg){i-extra+1,i+offset+extra-1,i,offset};
        #ifdef debug
        printf("%d %d\n",res.l,res.r);
        #endif
    }
    return res;
}
vector<Seg>seg_insert_lib;
void seg_insert(Seg a)
{
    seg_insert_lib.push_back(a);
}
void seg_commit()
{
    for(Seg a:seg_insert_lib)
    {
        seg_by_l[a.l].push_back(a);
        seg_by_r[a.r].push_back(a);
    }
    seg_insert_lib.clear();
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<=1;i++)
    {
        qpow_cache[i][0]=1;
        for(int j=1;j<=2*n;j++)
        {
            qpow_cache[i][j]=qpow_cache[i][j-1]*BASE[i]%MOD[i];
        }
        inv_cache[i][2*n]=qpow(qpow_cache[i][2*n],MOD[i]-2,i);
        for(int j=2*n-1;j>=0;j--)
        {
            inv_cache[i][j]=inv_cache[i][j+1]*BASE[i]%MOD[i];
        }
    }
    for(int i=0;i<=1;i++)
    {
        scanf("%s",s[i]+1);
        for(int j=1;j<=n;j++)
        {
            pfx[i][j]=pfx[i][j-1]+Hash(s[i][j]);
        }
    }
    #ifdef debug_
    pfx[1][n].prt();
    (pfx[1][n-1]-pfx[1][1]).prt();
    (pfx[1][4]-pfx[1][0]).prt();
    (pfx[1][n]-pfx[1][1]).prt();
    printf("%d %d %d\n",(pfx[1][n-1]-pfx[1][1]).check(),pfx[1][n].check(),pfx[0][n].check());
    get_hash(1,2).prt();
    #endif
    for(int i=1;i<=n;i++)
    {
        for(int offset=0;(offset<=1)&&(i+offset<=n);offset++)
        {
            corner_pt=n;
            int extra=0;
            int left=1,right=min(i,n-(i+offset)+1);
            while(left<=right)
            {
                int mid=(left+right)>>1;
                if(get_hash(i-mid+1,i+offset+mid-1).check())
                {
                    extra=mid;
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
            if(extra==0)
            {
                continue;
            }
            #ifdef debug
            printf("i %d offset %d extra %d\n",i,offset,extra);
            #endif
            ans=max(ans,extra*2-(offset==0));
            corner_pt=i+offset+extra-1;
            extra=0;
            left=1,right=min(i,n+1-(i+offset)+1);
            while(left<=right)
            {
                int mid=(left+right)>>1;
                if(get_hash(i-mid+1,i+offset+mid-1).check())
                {
                    extra=mid;
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
            if(extra==0)
            {
                continue;
            }
            #ifdef debug
            printf("i %d offset %d extra %d\n",i,offset,extra);
            #endif
            ans=max(ans,extra*2-(offset==0));
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int offset=0;(offset<=1)&&(i+offset<=n);offset++)
        {
            corner_pt=1;
            int extra=0;
            int left=1,right=min(i,n-(i+offset)+1);
            while(left<=right)
            {
                int mid=(left+right)>>1;
                if(get_hash(i-mid+1+1,i+offset+mid-1+1).check())
                {
                    extra=mid;
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
            if(extra==0)
            {
                continue;
            }
            #ifdef debug
            printf("i %d offset %d extra %d\n",i,offset,extra);
            #endif
            ans=max(ans,extra*2-(offset==0));
            corner_pt=i-extra+1;
            extra=0;
            left=1,right=min(i+1,n-(i+offset)+1);
            while(left<=right)
            {
                int mid=(left+right)>>1;
                if(get_hash(i-mid+1+1,i+offset+mid-1+1).check())
                {
                    extra=mid;
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
            if(extra==0)
            {
                continue;
            }
            #ifdef debug
            printf("i %d offset %d extra %d\n",i,offset,extra);
            #endif
            ans=max(ans,extra*2-(offset==0));
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[0][i]!=s[1][i])
        {
            continue;
        }
        corner_pt=i;
        int extra=0;
        int left=1,right=min(i,n-i+1);
        while(left<=right)
        {
            int mid=(left+right)>>1;
            if(get_hash(i-mid+1,i+mid).check())
            {
                extra=mid;
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        ans=max(ans,extra*2);
    }
    printf("%d\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 3ms
memory: 50324kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

score: 30
Accepted
time: 6ms
memory: 49856kb

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

score: 30
Accepted
time: 3ms
memory: 49996kb

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

score: 30
Accepted
time: 10ms
memory: 49812kb

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

27

result:

ok single line: '27'

Test #5:

score: 30
Accepted
time: 4ms
memory: 49864kb

input:

1000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...

output:

987

result:

ok single line: '987'

Test #6:

score: 30
Accepted
time: 6ms
memory: 49820kb

input:

1000
aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...

output:

45

result:

ok single line: '45'

Test #7:

score: 30
Accepted
time: 8ms
memory: 49948kb

input:

1000
aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...

output:

45

result:

ok single line: '45'

Test #8:

score: 30
Accepted
time: 3ms
memory: 50460kb

input:

1000
aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...

output:

36

result:

ok single line: '36'

Test #9:

score: 30
Accepted
time: 3ms
memory: 49816kb

input:

1000
aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...

output:

50

result:

ok single line: '50'

Test #10:

score: 30
Accepted
time: 7ms
memory: 50288kb

input:

1000
aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...

output:

20

result:

ok single line: '20'

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 425ms
memory: 51272kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 409ms
memory: 56156kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 406ms
memory: 56624kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 20
Accepted
time: 406ms
memory: 56268kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 20
Accepted
time: 395ms
memory: 56444kb

input:

99999
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99999

result:

ok single line: '99999'

Subtask #3:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #16:

score: 50
Accepted
time: 399ms
memory: 56296kb

input:

100000
vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...

output:

10

result:

ok single line: '10'

Test #17:

score: 50
Accepted
time: 399ms
memory: 58764kb

input:

100000
fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...

output:

9

result:

ok single line: '9'

Test #18:

score: 50
Accepted
time: 499ms
memory: 56296kb

input:

100000
baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...

output:

40

result:

ok single line: '40'

Test #19:

score: 50
Accepted
time: 505ms
memory: 56268kb

input:

100000
babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...

output:

43

result:

ok single line: '43'

Test #20:

score: 50
Accepted
time: 537ms
memory: 58388kb

input:

100000
aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...

output:

75

result:

ok single line: '75'

Test #21:

score: 50
Accepted
time: 533ms
memory: 58388kb

input:

100000
aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...

output:

58

result:

ok single line: '58'

Test #22:

score: 50
Accepted
time: 517ms
memory: 56340kb

input:

100000
abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...

output:

67

result:

ok single line: '67'

Test #23:

score: 50
Accepted
time: 535ms
memory: 56208kb

input:

100000
bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...

output:

55

result:

ok single line: '55'

Test #24:

score: 50
Accepted
time: 462ms
memory: 56268kb

input:

100000
cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...

output:

25

result:

ok single line: '25'

Test #25:

score: 50
Accepted
time: 459ms
memory: 56296kb

input:

100000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...

output:

96421

result:

ok single line: '96421'

Test #26:

score: 50
Accepted
time: 0ms
memory: 47996kb

input:

5
pkusc
pkukp

output:

6

result:

ok single line: '6'