Power Strings

Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 37439   Accepted: 15467

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
唉,太气人了,数组刚开始开小了。
开成char a[1000000];应该再大一些。

#include<stdio.h>
#include<string.h>
char a[1000100];
//int len;
char p[1000100];
int kmp()
{
	int i,j,len;
	i=0,j=-1;
	p[0]=-1;
	len=strlen(a);
	while(i<len)
	{
		if(j==-1||a[i]==a[j])
		{
			i++;j++;
			//printf("%d ",j);
			p[i]=j;
		}
		else j=p[j];
	//	printf("%d\n",j);
	}
	i=len-j;
	if(len%i==0)
		{
			return len/i;
		}
		return 1;
}
int main()
{
	int c;
	while(scanf("%s",a)&&a[0]!='.')
	{
		c=kmp();
		printf("%d\n",c);
	}
	return 0;
} 

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-06

Power Strings的相关文章

Power Strings(KMP)

Power Strings Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 45008   Accepted: 18794 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 = "

POJ 2406 Power Strings

F - Power Strings Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Practice POJ 2406 Description Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = &

G - Power Strings POJ 2406 (字符串的周期)

G - Power Strings Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 2406 Description Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def

Power Strings (poj 2406 KMP)

Language: Default 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"

UVa 10298 - Power Strings

题目:求一个串的最大的循环次数. 分析:dp,KMP,字符串.这里利用KMP算法. KMP的next函数是跳跃到最近的串的递归结构位置(串元素取值0 ~ len-1): 由KMP过程可知: 如果存在循环节,则S[0 ~ next[len]-1] 与 S[len-next[len] ~ len-1]相匹配: 则S[next[len] ~ len-1]就是循环节(且最小),否则next[len]为0: 因此,最大循环次数为len/(len-next[len]),最小循环节为S[next[len] ~

poj 2406 Power Strings KMP匹配

对于数组s[0~n-1],计算next[0~n](多计算一位). 考虑next[n],假设t=n-next[n],如果n%t==0,则t就是问题的解,否则解为1. 这样考虑: 比如字符串"abababab", a  b a b a b a b * next     -1 0 1 2 3 4 5 6  7 考虑这样的模式匹配,将"abababab#"当做主串,"abababab*"当做模式串,于是进行匹配到n(n=8)时,出现了不匹配: 主串   

POJ2406 Power Strings 【KMP】

Power Strings Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 31388   Accepted: 13074 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 = "

POJ 2406 Power Strings KMP运用题解

本题是计算一个字符串能完整分成多少一模一样的子字符串. 原来是使用KMP的next数组计算出来的,一直都觉得是可以利用next数组的,但是自己想了很久没能这么简洁地总结出来,也只能查查他人代码才恍然大悟,原来可以这么简单地区求一个周期字符串的最小周期的. 有某些大牛建议说不应该参考代码或者解题报告,但是这些大牛却没有给出更加有效的学习方法,比如不懂KMP,难倒不应该去看?要自己想出KMP来吗?我看不太可能有哪位大牛可以直接自己"重新创造出KMP"来吧. 好吧,不说"创造KMP

(求循环节的个数)Power Strings -- poj -- 2406

链接: http://poj.org/problem?id=2406 Power Strings Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Description Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc&qu

poj 2406 Power Strings 【kmp】

Power Strings Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 37564   Accepted: 15532 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 = "