poj-2406 Power Strings

绝地灬酷狼 2021-11-01 04:26 217阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;65854</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;27197</td> 
  </tr> 
 </tbody> 
</table>

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

abcd
    aaaa
    ababab
    .

Sample Output

1
    4
    3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

思路：next\[i\]表示以第i个字符结束的最大后缀和最大前缀相等。n-next\[n\]则为最小的循环节。若n%(n-next\[n\])==0,那么n/(n-next\[n\])则为循环节出现的最大次数。

#include <iostream>
    #include<string.h>
    using namespace std;
    const int maxn = 1e6+10;
    char a[maxn];
    int ne[maxn];
    int main()
    {
        while(scanf("%s",a+1)&&a[1]!='.')
        {
            memset(ne,0,sizeof(ne));
            int len = strlen(a+1);
            for(int i=2,j=0;i<=len;i++)
            {
                while(j&&a[i]!=a[j+1]) j=ne[j];
                if(a[i]==a[j+1]) j++;
                ne[i]=j;
            }
            if(len%(len-ne[len])==0) printf("%d\n",len/(len-ne[len]));
            else
                printf("1\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wjc2021/p/11300065.html