首页 > 代码库 > POJ - 2406 Power Strings
POJ - 2406 Power Strings
题目来源：http://poj.org/problem?id=2406
主要考察KMP算法中next数组的性质，根据next[len]可以知道前len-1字符串最长前缀和后缀的循环长度
那么len-next[len]即为一个循环单位的长度，倘若循环单位len-next[len]不是len的整数倍，则ans=1。
1 #include<stdio.h> 2 #include<string.h> 3 const int maxn=1000000; 4 char s[maxn]; 5 int next[maxn]; 6 void get_next(int len) 7 { 8 int i=0,j=-1; 9 next[0]=-1;10 while(i<len){11 if(j==-1 || s[i]==s[j])12 next[++i]=++j;13 else14 j=next[j];15 }16 }17 int main()18 {19 while(scanf("%s",s)!=EOF){20 if(s[0]==‘.‘)21 break;22 int len=strlen(s);23 get_next(len);24 int modans=len%(len-next[len]);25 if(modans)26 printf("1\n");27 else28 printf("%d\n",len/(len-next[len]));29 }30 return 0;31 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。