首页 > 代码库 > E - Power Strings,求最小周期串
E - Power Strings,求最小周期串
E - Power Strings
Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uDescription
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
abcdaaaaababab.
Sample Output
143
讲了这么多,其实就是一个求一个字符串里最小周期的问题。限时有3S,我们可以用枚举。
这里需要注意的是一个:求周期串的基本算法:
for(i=1;i<=len;i++)
{
ok=1;
if(len%i==0)
{
for(j=i;j<len;j++)
{
if(s[j]!=s[j%i]){ok=0;break;}
}
}
if(ok==1)
{
printf("%d\n",len/i);
break;//记得要break
}
}
1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 char s[1000100]; 5 int main() 6 { 7 while(scanf("%s",s)==1&&strcmp(s,".")!=0) 8 { 9 int len=strlen(s);10 11 for(int i=1;i<=len;i++)12 if(len%i==0)13 {14 int ok=1;15 for(int j=i;j<len;j++)16 {17 if(s[j]!=s[j%i])18 {19 ok=0;20 break;21 }22 }23 if(ok)24 {25 printf("%d\n",len/i);26 break;27 }28 29 }30 }31 return 0;32 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。