本文主要是介绍hdu3746Cyclic Nacklace，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
给你一串字符（a~b)，问你最少需要在末尾添加多少个字符，使得这串字符形成一个循环，如abcab需要在末尾添加一个c即可.
解题思路：
其实就是next数组的应用。
当next[n]*2>=n的时候，必然出现了循环节，我们只要就出最小的循环节，pre=(n-(next[n]))然后,如果n%pre==0,的话就是说刚好形成的n/pre个循环，就不必再添加了，但是如果n%pre！=0,那么n-(n%pre)就是还需要添加的。
当next[n]*2<n就是说一个循环都还没形成，那么n-next[n]就是需要添加的字符数。
#include<stdio.h>
#include<string.h>
#define N 100009
int next[N];
int get_next(int n,char *p){int i=0,j=-1;next[i]=j;while(i<n){if(j==-1||p[i]==p[j]){i++;j++;next[i]=j;}else{j=next[j];}}return next[n];
}
void getans(int len,int k){if(2*k<len){printf("%d\n",len-2*k);return ;}else{int pre=len-k;if(len%pre==0){printf("0\n");return ;}else{printf("%d\n",pre-(k%pre));return ;}}return ;
}
int main()
{char buff[N];int t,len,j;scanf("%d",&t);getchar();while(t--){gets(buff);len=strlen(buff);j=get_next(len,buff);getans(len,j);}return 0;}
这篇关于hdu3746Cyclic Nacklace的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
