|
Language: Default
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 |
定理：如果S的长度为len。则S存在循环子串，当且仅当，len能够被len - next[len]整除，最短循环子串为S[len - next[len]]
思路：利用KMP算法，求字符串的特征向量next，若len能够被len - next[len]整除。则最大循环次数n为len/(len - next[len])，否则为1。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int N;
int nextval[1000010];
char str[1000010];
int get_nextval()
{
int i=0;
int len=strlen(str);
int j=-1;
nextval[i]=-1;
while (i<len)
{
if (j==-1||str[i]==str[j])
{
i++;
j++;
nextval[i]=j;
}
else
j=nextval[j];
}
if ((len)%(len-nextval[len])==0)
return len/(len-nextval[len]);
else
return 1;
}
int main()
{
while (scanf("%s",str))
{
if (str[0]=='.')
return 0;
printf("%d\n",get_nextval());
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4636202.html，如需转载请自行联系原作者
