题意

求字符串s的最小循环元长度和循环次数

思路

s[1~i]满足循环元要len能整除i并且s[len+1~i]=s[1~i-len]

代码

#include<cstdio> #include<algorithm> #include<cstring> #define N 1000005 using namespace std; char s[N]; int next[N]; int n,T; int len; void kmp() { next[1]=0; for(int i=2,j=0;i<=len;i++) { while(j>0&&s[i]!=s[j+1]) j=next[j]; if(s[i]==s[j+1]) j++; next[i]=j; } } int main() { while(scanf("%d",&n)==1&&n) { scanf("%s",s+1); len=strlen(s+1); kmp(); printf("Test case #%d\n",++T); for(int i=2;i<=n;i++) { if(i%(i-next[i])==0 && i/(i-next[i])>1) printf("%d %d\n",i,i/(i-next[i])); } puts(""); } return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10198490.html