Power Strings (poj 2406 KMP)

Language:

Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 33205		Accepted: 13804

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.

Source

Waterloo local 2002.07.01

题意：给一个字符串S长度不超过10^6，求最大的n使得S由n个同样的字符串a连接而成。如："ababab"则由n=3个"ab"连接而成。"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。

定理：如果S的长度为len。则S存在循环子串，当且仅当，len能够被len - next[len]整除，最短循环子串为S[len - next[len]]

思路：利用KMP算法，求字符串的特征向量next，若len能够被len - next[len]整除。则最大循环次数n为len/(len - next[len])，否则为1。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int N;
int nextval[1000010];
char str[1000010];

int get_nextval()
{
    int i=0;
    int len=strlen(str);
    int j=-1;
    nextval[i]=-1;
    while (i<len)
    {
        if (j==-1||str[i]==str[j])
        {
            i++;
            j++;
            nextval[i]=j;
        }
        else
            j=nextval[j];
    }
    if ((len)%(len-nextval[len])==0)
        return len/(len-nextval[len]);
    else
        return 1;
}

int main()
{
    while (scanf("%s",str))
    {
        if (str[0]=='.')
            return 0;
        printf("%d
",get_nextval());
    }
    return 0;
}