POJ 1961 2406 (KMP,最小循环节,循环周期)

关于KMP的最短循环节、循环周期,请戳:

http://www.cnblogs.com/chenxiwenruo/p/3546457.html (KMP模板,最小循环节)

POJ 2406  Power Strings

题意:
给一个字符串,问这个字符串是否能由另一个字符串重复R次得到,求R的最大值。

#include <iostream>
#include <stdio.h>
#include <string.h>
/*
题意:
给一个字符串,问这个字符串是否能由另一个字符串重复R次得到,求R的最大值。
*/
using namespace std;
const int maxn=;
int next[maxn];
char str[maxn];
void getnext(char *str,int len){
next[]=-;
int i=,j=-;
while(i<len){
if(j==-||str[i]==str[j]){
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
while(scanf("%s",str)!=EOF){
if(str[]=='.')
break;
int len=strlen(str);
getnext(str,len);
int l=len-next[len];
if(len%l==)
printf("%d\n",len/l);
else
printf("1\n");
}
return ;
}

POJ 1961  Period

给你一个字符串,对于它长度为i的前缀(i=2~n),给出对应的循环周期k,即前缀可由某个字符串拼接k次得到(k>1)
2406的加强版

#include <iostream>
#include <stdio.h>
#include <string.h>
/*
给你一个字符串,对于它长度为i的前缀(i=2~n),给出对应的循环周期k,即前缀可由某个字符串拼接k次得到(k>1)
2406的加强版
*/
using namespace std;
const int maxn=;
int next[maxn];
char str[maxn];
int n;
void getnext(char*str,int len){
next[]=-;
int i=,j=-;
while(i<len){
if(j==-||str[i]==str[j]){
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
int cases=;
while(scanf("%d",&n),n){
scanf("%s",str);
getnext(str,n);
printf("Test case #%d\n",++cases);
for(int i=;i<=n;i++){
int l=i-next[i];
if(i%l== && i/l>){
printf("%d %d\n",i,i/l);
}
}
printf("\n");
}
return ;
}
上一篇:android 7.0以上charles https抓包


下一篇:jdk安装环境变量设置