首页 > 代码库 > poj2406 kmp 求最小循环字串
poj2406 kmp 求最小循环字串
Power Strings
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 47748 | Accepted: 19902 |
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.
题意：
给你一个字符串，求该字符串最多由多少个循环字串构成。
题解：
定义一个整型变量 m; //m表示字符串长度
用kmp里的next数组 求出字符串的最长前缀长度，然后判断 m 是否能被 m-next[m] 整除，即 m%(m-next[m])是否等于0，如果能被整除，m-next[m]为最短循环字串，否则最短循环字串长度等于整个字符串长度。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int next[1000002];
char a[1000002];
void getNext()
{
int i=-1,j=0;
next[0]=-1;
int cnt=0;
while(a[j])
{
if(a[i]==a[j]||i==-1)
{
next[++j]=++i;
}
else
i=next[i];
}
}
int main()
{
while(scanf("%s",a)!=EOF)
{
if(a[0]==‘.‘) break;
int m=strlen(a);
getNext();
int cc=1;
if(m%(m-next[m])==0) //如果条件满足，m-next[m]为最短循环字串，然后求出该字符串由多少个最短循环字串构成
cc=m/(m-next[m]);
cout<<cc<<endl;
}
return 0;
}
poj2406 kmp 求最小循环字串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。