分析:
1 题目要求的是给定一个字符串,问我们还需要添加几个字符可以构成一个由n个循环节组成的字符串。
2 可知我们应该先求出字符串的最小循环节的长度:假设字符串的长度为len,那么最小的循环节就是cir = len-next[len] ; 如果有len%cir == 0,那么这个字符串就是已经是完美的字符串,不用添加任何字符;如果不是完美的那么需要添加的字符数就是cir - (len-(len/cir)*cir)),相当与需要在最后一个循环节上面添加几个。
3 如果cir = 1,说明字符串只有一种字符例如“aaa” ; 如果cir = m说明最小的循环节长度为m,那么至少还需m个;如果m%cir == 0,说明已经不用添加了。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 100010 int t; char pattern[MAXN]; int next[MAXN]; /*求next数组*/ void getNext(){ int m = strlen(pattern); next[0] = next[1] = 0; for(int i = 1 ; i < m ; i++){ int j = next[i]; while(j && pattern[j] != pattern[i]) j = next[j]; next[i+1] = pattern[i] == pattern[j] ? j+1 : 0; } /*求最小的循环节*/ int cir = m-next[m]; if(cir == 1) printf("0\n"); else if(cir == m) printf("%d\n" , m); else if(cir != m && m%cir == 0) printf("0\n"); else{ int num = m/cir;/*求出有几个循环节*/ printf("%d\n" , cir-(m-cir*num)); } } int main(){ scanf("%d" , &t); while(t--){ scanf("%s%*c" , pattern); getNext(); } return 0; }