KMP与循环节相关题目

HDU 3746 Cyclic Nacklace ( KMP求最小循环节 )

len - nextval[len]即为最小循环节长度。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int MAXN = ;

const int INF  =  << ;

char str[MAXN];

int nextval[MAXN];

int len;

void getNext( char s[], int next[] )

{

    int length=len;

    int i=,j=-;

    next[]=-;

    while(i<length)

    {

        if(j==-||s[i]==s[j])

        {

            ++i;

            ++j;

            next[i]=j;

        }

        else

            j=next[j];

    }

}

int main()

{

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%s", str );

        len = strlen(str);

        getNext( str, nextval );

        int sub = len - nextval[len];

        if ( sub != len && len % sub ==  ) puts("");

        else printf( "%d\n", sub - ( nextval[len]%sub ) );

    }

    return ;

}

HDU 1358 Period

题意：若某串的前i个字符是循环串，输出i以及循环节出现的次数。

做法跟上一题差不多

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int MAXN = ;

char str[MAXN];

int nextval[MAXN];

int len;

void getNext( char s[], int next[] )

{

    int length=len;

    int i=,j=-;

    next[]=-;

    while(i<length)

    {

        if(j==-||s[i]==s[j])

        {

            ++i;

            ++j;

            next[i]=j;

        }

        else

            j=next[j];

    }

}

int main()

{

    int cas = ;

    while ( scanf( "%d", &len ), len )

    {

        scanf( "%s", str );

        getNext( str, nextval );

        printf( "Test case #%d\n", ++cas );

        for ( int i = ; i <= len; ++i )

        {

            int sub = i - nextval[i];

            if ( i / sub >  && i % sub ==  )

            {

                printf("%d %d\n", i, i / sub );

            }

        }

        puts("");

    }

    return ;

}

POJ 2406 Power Strings（求循环串的最大循环周期）

注意这组数据：aabaabaa

显然答案是：1

#include <cstdio>

#include <cstring>

#include <cstdlib>

const int MAXN = ;

char str[MAXN];

int nextval[MAXN];

int len;

void getNext(char s[],int next[])

{

    int length=len;

    int i=,j=-;

    next[]=-;

    while(i<length)

    {

        if(j==-||s[i]==s[j])

        {

            ++i;

            ++j;

            next[i]=j;

        }

        else

            j=next[j];

    }

}

int main()

{

    while ( scanf( "%s", str ) ==  && str[] != '.' )

    {

        len = strlen(str);

        getNext( str, nextval );

        int sub = len - nextval[len];

        if ( len % sub ==  ) printf("%d\n", len / sub );

        else printf("1\n");

    }

    return ;

}

巴特西

KMP与循环节相关题目

最新文章

热门文章