国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > poj 2406 Power Strings【KMP】

poj 2406 Power Strings【KMP】

来源:程序员人生   发布时间:2014-12-20 09:11:27 阅读次数:2785次
点击打开题目
Power Strings
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 33548   Accepted: 13935

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.
题目翻译意:给1个字符串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<cstdio> #define maxn 1000002 char str[maxn]; int next[maxn],len,s; void GetNext(){ int i=0,j=⑴; next[0]=⑴; while(str[i]){ if(j==⑴||str[i]==str[j]){ ++i;++j;next[i]=j; }else j=next[j]; } len=i; } int main(){ while(scanf("%s",str)==1){ if(str[0]=='.') break; GetNext(); s=len-next[len]; if(len%s==0) printf("%d ",len/s); else printf("1 "); }return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生