ZOJ1905Power Strings （KMP||后缀数组+RMQ求循环节）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters.

<b< dd="">

Output

For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

求最大循环长度。

KMP可以求，之前做过，见。

http://www.cnblogs.com/hua-dong/p/8016873.html

http://www.cnblogs.com/hua-dong/p/8016916.html

这里实现了后缀数组(不过好像被卡了，只能同KMP实现)。

#include<cmath>

#include<cstdio>

#include<string>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

int min(int x,int y) { if(x<y) return x;return y;}

using namespace std;

const int maxn=;

char ch[maxn];

struct SA

{

    int Rank[maxn],sa[maxn],tsa[maxn],A[maxn],cntA[maxn],B[maxn],cntB[maxn];

    int ht[maxn],Min[maxn][],N;

    void get_SA()

    {

        N=strlen(ch+);

        for(int i=;i<=;i++) cntA[i]=;

        for(int i=;i<=N;i++)  cntA[ch[i]]++;

        for(int i=;i<=;i++) cntA[i]+=cntA[i-];

        for(int i=N;i>=;i--)  sa[cntA[ch[i]]--]=i;

        Rank[sa[]]=;

        for(int i=;i<=N;i++)  Rank[sa[i]]=Rank[sa[i-]]+(ch[sa[i]]==ch[sa[i-]]?:);

        for(int l=;Rank[sa[N]]<N;l<<=){

            for(int i=;i<=N;i++) cntA[i]=cntB[i]=;

            for(int i=;i<=N;i++) cntA[A[i]=Rank[i]]++;

            for(int i=;i<=N;i++) cntB[B[i]=i+l<=N?Rank[i+l]:]++;

            for(int i=;i<=N;i++) cntA[i]+=cntA[i-],cntB[i]+=cntB[i-];

            for(int i=N;i>=;i--) tsa[cntB[B[i]]--]=i;

            for(int i=N;i>=;i--) sa[cntA[A[tsa[i]]]--]=tsa[i];

            Rank[sa[]]=;

            for(int i=;i<=N;i++) Rank[sa[i]]=Rank[sa[i-]]+(A[sa[i]]==A[sa[i-]]&&B[sa[i]]==B[sa[i-]]?:);

        }

    }

    void get_hgt()

    {

        for(int i=,j=;i<=N;i++){

            if(j) j--;

            while(ch[i+j]==ch[sa[Rank[i]-]+j]) j++;

            ht[Rank[i]]=j;

        }

    }

    void get_rmq()

    {

        for(int i=;i<=N;i++) Min[i][]=ht[i];

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

         for(int j=;j+(<<i)-<=N;j++){

              Min[j][i]=min(Min[j][i-],Min[j+(<<(i-))][i-]);

         }

    }

    int query_rmq(int L,int R)

    {

        if(L>R) swap(L,R);L++;

        int k=log2(R-L+);

        return min(Min[L][k],Min[R-(<<k)+][k]);

    }

    void solve()

    {

        int ans=;

        for(int i=;i<=N;i++){

            if(N%i!=) continue;

            if(i+query_rmq(Rank[],Rank[+i])==N) {

                ans=N/i; break;

            }

        }   printf("%d\n",ans);

    }

}Sa;

int main()

{

    while(~scanf("%s",ch+)){

        if(ch[]=='.') return ;

        Sa.get_SA();

        Sa.get_hgt();

        Sa.get_rmq();

        Sa.solve();

    }  return ;

}