Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 31111		Accepted: 12982

Description

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

Output

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

Sample Input

abcdaaaaababab.

Sample Output

143

题意：输出循环节最大的个数

思路：next函数推断一下就可以：

若n%(n-next[n])==0 ans = n/(n-next[n])

否则 ans = 1

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 1000000+10;int next[maxn];char str[maxn];int n;void getNext(){ next[0] = next[1] = 0; for(int i = 1,j; i < n; i++){ j = next[i]; while(j && str[i] != str[j]) j = next[j]; if(str[i]==str[j]) next[i+1] = j+1; else next[i+1] = 0; }}int main(){ while(~scanf("%s",str) && strcmp(str,".")!=0){ n = strlen(str); getNext(); int ans; if(n%(n-next[n])!=0) ans = 1; else ans = n/(n-next[n]); printf("%d\n",ans); } return 0;}