首页 > 代码库 > poj 2406 Power Strings 【KMP的应用】

poj 2406 Power Strings 【KMP的应用】

2024-08-05 12:12:19   218人阅读

Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 33595 Accepted: 13956

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.

比赛的时候看错题意了55555

求出next数组，判断最后一位除以（最后一位减去next【最后一位】）的长度，如果大于1，输出商，否则1

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

const int M = 1000010;
const int INF = 0x3f3f3f3f;

char s[M];
int next[M];

void getnext(){
	int len = strlen(s);
	next[0] = -1;
	int i = 0, j = -1;
	while(i <len){
		if(j == -1||s[i] == s[j]){
			++i;++j; next[i] = j;
		}
		else j = next[j];
	}
}

int main(){
	while(gets(s), s[0] != '.'){
		getnext();
		int max = 0;
		int i = 0;
		/*for(; i <= strlen(s); i ++){
			int temp = i-next[i];
			if(i%temp == 0&&max < i/temp){
				max = i/temp;
			}
		}*/
		int temp = strlen(s)-next[strlen(s)];
		if(strlen(s)%temp == 0) max = strlen(s)/temp;
		if(max > 1) printf("%d\n", max);
		else printf("%d\n", 1);
	}
	return 0;
}



poj 2406 Power Strings 【KMP的应用】


联系
我们