首页 » 字符串-KMP » 正文

POJ – 2406 Power Strings(KMP)

Power Strings

来源:http://poj.org/problem?id=2406

Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 58869 Accepted: 24457

Description

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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

解法

其实就是循环节的次数,如果不能表示成循环节的个数,就是单独的一。

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>

using namespace std;  

const int maxn = 1001000;  

char arrn[maxn];  

void preKMP(char x[], int m, int kmpNext[]){
    int i, j;  
    j=kmpNext[0]=-1;  
    i=0;  
    while(i < m){
        while(-1 != j && x[i] != x[j]) j = kmpNext[j];  
        kmpNext[++i] = ++j;  
    }
}

int nxt[maxn];  

int main(){
    //freopen("in.txt", "r", stdin);  
    int n;  
    while(~scanf("%s", arrn)){
        if(arrn[0] == '.') break;  
        int n = strlen(arrn);  
        preKMP(arrn, n, nxt);  
        int len = n - nxt[n];  
        if( n % len )printf("1\n");  //不能表示为循环节
        else printf("%d\n",  n/len);  
    }

    return 0;  
}

发表评论