[POJ 2406]Power Strings[KMP]

Description
We denote the concatenation of two strings a and b as a * b. An illustrative example demonstrates that when two strings are concatenated, such as when a is equal to 'abc' and b is equal to 'def', their product becomes 'abcdef'. Exponentiation with respect to string concatenation is analogous to multiplication in numerical systems. Specifically, for any non-negative integer n, the expression a^0 corresponds to the empty string, denoted by ''. Furthermore, for n greater than zero, the operation is recursively defined as multiplying the base string by itself n times: a^{(n+1)} equals the result of concatenating string a with its n^{th} power.

Every test case represents a single line of input, denoting a string composed exclusively of printable characters. The length of the string s must be at least one character but cannot exceed one million characters. Following the last test case, there will be an additional line consisting solely of a period.

Given any string s, you must compute the maximum possible value of n such that there exists a string a where s = a^n.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

This problem receives a large amount of input data. Instead of using the standard input stream cin, it's recommended to employ scanf for better performance and to prevent potential time limit exceeded scenarios.

Source
Waterloo local 2002.07.01

对于给定字符串S，请确定其最小循环周期。

进一步分析可知，在KMP算法中,next数组记录了模式串中每个位置i在出现字符不匹配时的回退位置,next[i]表示当模式串第i个字符与文本串第j个字符不匹配时,需要回退到下一个可能的位置继续匹配。

进而可知,模式串从位置1到next[n],以及从(n - next[n])+1到n的位置段内,对应的字符序列是完全相同的。

由此可知,若n能被（n - next[n]）整除,则该模式字符串包含一个长度为（n - next[n]）的连续重复子串。

其最小循环节长度即为（length of S - next[length of S]）。

例如：a b a b a b

next:-1 0 0 1 2 3 4

next[n]等于4时，则表明前缀"abab"与后缀"abab"的最大相同长度；这进一步表明，“a”和“b”这两个字符构成了一个循环节，并且其循环节的长度为n - next[n]；

    #include<iostream>
    #include<string.h>
    using namespace std;
    int next[1000005];
    char s[1000005];
    void getnext()
    {
    int i=0,j=-1;
    next[0]=-1;
    int len=strlen(s);
    while(i<len)
    {
        if(s[i]==s[j]||j==-1)
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
    }
    int main()
    {
    while(scanf("%s",s)>0)
    {
        if(s[0]=='.')
            break;
        int len=strlen(s);
        getnext();
        if(len%(len-next[len])==0)
            printf("%d\n",len/(len-next[len]));
        else
            printf("1\n");
    }
    return 0;
    }