Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 27003		Accepted: 11311

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).

Each test case is a line of input representing s, a string of printable characters. 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.

For each s you should print the largest n such that s = a^n for some string a.

abcd

aaaa

ababab

.

1

4

3

思路：
理解next数组，利用next数组进行巧妙求解

 #include<iostream>

 #include<string.h>

 #include<stdio.h>

 using namespace std;

 #define MAX 1000000

 void get_next(char *str,int *next)

 {

     int i=,j=-;

     int tlen=strlen(str);

     next[]=-;

     while(i<tlen)

     {

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

         {

             i++;

             j++;

             if(str[i]!=str[j])

                 next[i]=j;

             else

                 next[i]=next[j];

         }

         else

             j=next[j];

     }

 }

 char str[MAX+];

 int next[MAX+];

 int main()

 {

     int t=;

     while(~scanf("%s",str))

     {

         if(str[]=='.')  break;

         get_next(str,next);

         int len = strlen(str);

     //    for(int i=0;i<=len;i++)  cout<<next[i]<<" "; cout<<endl;

         if(len%(len-next[len])==)  //next[len]为匹配到len时失配所要跳到的上一个匹配点，len-next[len]即为一个循环节

             printf("%d\n",len/(len-next[len]));

         else

             printf("1\n");

     }

     return ;

 }

 #include <iostream>

 #include <stdio.h>

 #include<string.h>

 using namespace std;

 #define maxn 1100000

 #define cls(x) memset(x, 0, sizeof(x))

 int wa[maxn],wb[maxn],wv[maxn],wss[maxn];

 int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}

 //倍增算法

 void da(char *r,int *sa,int n,int m)

 {

      cls(wa);

      cls(wb);

      cls(wv);

      int i,j,p,*x=wa,*y=wb,*t;

      //基数排序

      for(i=;i<m;i++) wss[i]=;

      for(i=;i<n;i++) wss[x[i]=r[i]]++;

      for(i=;i<m;i++) wss[i]+=wss[i-];

      for(i=n-;i>=;i--) sa[--wss[x[i]]]=i;

      //　在第一次排序以后，rank数组中的最大值小于p，所以让m=p。整个倍增算法基本写好，代码大约25行。

      for(j=,p=;p<n;j*=,m=p)

      {

        //接下来进行若干次基数排序，在实现的时候，这里有一个小优化。基数排序要分两次，第一次是对第二关键字排序，第二次是对第一关键字排序。对第二关键字排序的结果实际上可以利用上一次求得的sa直接算出，没有必要再算一次

        for(p=,i=n-j;i<n;i++) y[p++]=i;

        for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

        //其中变量j是当前字符串的长度，数组y保存的是对第二关键字排序的结果。然后要对第一关键字进行排序，

        for(i=;i<n;i++) wv[i]=x[y[i]];

        for(i=;i<m;i++) wss[i]=;

        for(i=;i<n;i++) wss[wv[i]]++;

        for(i=;i<m;i++) wss[i]+=wss[i-];

        for(i=n-;i>=;i--) sa[--wss[wv[i]]]=y[i];

        //这样便求出了新的sa值。在求出sa后，下一步是计算rank值。

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

        x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

      }

 }

 int rank[maxn],height[maxn];

 //得到height数组：排名相邻的两个后缀的最长公共前缀

 void calheight(char *r,int *sa,int n)

 {

      cls(rank);

      cls(height);

      int i,j,k=;

      for(i=;i<n;i++) rank[sa[i]]=i;

     // for(i=0;i<n;i++)  printf("%d ",rank[i]); putchar(10); system("pause");

      for(i=;i<n;height[rank[i++]]=k)

          for(k?k--:,j=sa[((rank[i]-<)?:rank[i]-)];r[i+k]==r[j+k]&&i!=j;k++);

      return;

 }

 char ca[maxn];

 int sa[maxn];

 int N;

 int minh[maxn];

 int main()

 {

     int i;

     while (~scanf("%s",ca))

     {

         N = strlen(ca);

         if(ca[]=='.')   break;

         ca[N] = '#';

         N++;

         da(ca, sa, N, );

         calheight(ca,sa,N);

      //  for(i=0;i<N;i++)  cout<<rank[i]<<" "; cout<<endl;

      //   for(i=0;i<N;i++)  cout<<height[i]<<" "; cout<<endl;

      //   for(i=0;i<N;i++)  cout<<sa[i]<<" "; cout<<endl;

         int i;

         int mins = height[rank[]];

         for(i=rank[];i>;i--)

         {

             if(mins>height[i])

             {

                 mins = height[i];

             }

             minh[i-] = mins;

         }

         mins = height[rank[]];

         for(i=rank[];i<N;i++)

         {

             if(mins>height[i])

             {

                 mins = height[i];

             }

             minh[i] = mins;

         }

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

          {

             if ((N-) % i==&&minh[rank[i]]==N--i)

             {

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

                 break;

             }

          }

     }

     return ;

 }