首页 > 代码库 > Uva 12012 Detection of Extraterrestrial 求循环节个数为1-n的最长子串长度 KMP
Uva 12012 Detection of Extraterrestrial 求循环节个数为1-n的最长子串长度 KMP
题目链接:点击打开链接
题意:
给定一个字符串str 求字符串str的
循环节个数为 1-len 个的
最长子串长度
思路:套用kmp的性质
#include<string.h> #include<stdio.h> #include <iostream> using namespace std; #define n 1300 void getnext(char str[n],int next[n]){ int m=strlen(str); next[0]=next[1]=0; for(int i=1;i<m;i++){ int j=next[i]; while(j&&str[i]!=str[j])j=next[j]; next[i+1]= str[i]==str[j] ? j+1 : 0; } } int Inext[n],f[n]; char Istr[n],c[n]; int main() { int i,k,j,t,l=1,g; scanf("%d",&t); while(t--) { memset(f,0,sizeof(f)); scanf("%s",Istr); int len=strlen(Istr); for(i=0;i<len;i++) { k=0; for(j=i;j<len;j++)c[k++]=Istr[j]; c[k]=0; getnext(c,Inext); for(j=1;j<=k;j++) //扫一遍失配数组 if(j%(j-Inext[j])==0) { for(g=1;g<=j/(j-Inext[j]);g++) if((j/(j-Inext[j]))%g==0) f[g]=max(f[g],j); } } f[1]=len; printf("Case #%d:",l++); for(i=1;i<=len;i++) printf(" %d",f[i]); puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。