|
Power Strings
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.
Source |
题意：
给你一个字符串。问你这个字符串最多可以由一个子串重复多少次得到。
思路：
和大白(刘汝佳 训练指南)类似。先获取失配数组。然后匹配文本尾。len-f[i]就为循环节长度。
详细见代码：
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1000100;
int f[maxn];
char txt[maxn];
void getf(char *p)
{
int i,j,m=strlen(p);
f[0]=f[1]=0;
for(i=1;i<m;i++)
{
j=f[i];
while(j&&p[i]!=p[j])
j=f[j];
f[i+1]=p[i]==p[j]?j+1:0;
}
}
int main()
{
int len,i,ans,t;
while(~scanf("%s",txt))
{
if(txt[0]=='.')
break;
getf(txt);
len=strlen(txt);
i=len;
ans=1;
while(f[i])
{
t=len-f[i];
if(len%t==0&&len/t>ans)
ans=len/t;
i=f[i];
}
printf("%d\n",ans);
}
return 0;
}