HDU 3746

http://acm.hdu.edu.cn/showproblem.php?pid=3746

kmp的Nxet数组求字符串循环节例题

lenB%(lenB-Next[lenB])==0则其有周期lenB/(lenB-Next[lenB])，其中最小循环节长度是lenB-Next[lenB]

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std ;

char B[] ;

int Next[],lenB ;

void GetNext()

{

    int i,j ;

    Next[]= ;

    j= ;

    for(i= ;i<=lenB ;i++)

    {

        while(j> && (B[j+]!=B[i]))j=Next[j] ;

        if(B[j+]==B[i])j++ ;

        Next[i]=j ;

    }

}

int main()

{

    int t ;

    scanf("%d",&t) ;

    while(t--)

    {

        scanf("%s",B+) ;

        lenB=strlen(B+) ;

        GetNext() ;

        int minn=lenB-Next[lenB] ;

        if(!Next[lenB])printf("%d\n",lenB) ;

        else if(lenB%minn)

            printf("%d\n",minn-lenB%minn) ;

        else

            printf("0\n") ;

    }

    return  ;

}