首页 > 代码库 > poj 1961 Period
poj 1961 Period
链接:poj 1961
题意:给你一个字符串,求这个字符串首字符到第i个字符为止的子串的最大循环次数k(k>1),若存在,输出i和k.
比如aabaabaabaab,长度为12.
到第2个字符时,a出现2次,到第6个字符时,aab出现了2次,
到第9个字符时,aab出现3次,到第12个字符时,aab出现4次
分析:这个就是求给定字符串的前缀子串(包括整个串)的最大循环次数,根据next数组即可
if(n%(n-next[n])==0)
最小循环长度为 L=n-next[n];
最大循环次数为 S=n/L=n/(n-next[n]);
#include<stdio.h> #include<string.h> int next[1001010]={-1}; char s[1001010]; void getnext(int n) { int i=0,j=-1; while(i<n){ if(j==-1||s[i]==s[j]){ i++; j++; next[i]=j; } else j=next[j]; } } int main() { int n,i,j,k=0,m; while(scanf("%d",&n)!=EOF){ if(n==0) break; scanf("%s",s); k++; printf("Test case #%d\n",k); getnext(n); for(i=1;i<n;i++){ j=i+1; if(j%(j-next[j])==0){ m=j/(j-next[j]); if(m>1) printf("%d %d\n",j,m); } } printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。