Description

求最少需要在给定字符串后面补几个字符才能凑成至少两个循环

Solution

对KMP中p数组的灵活引用

首先，n-p[n]为为字符串的最小循环节，如果(n%(n-p[n]))==0那么不需要补字符

否则的话，应补的字符数最少应为(n-p[n])-n%(n-p[n])

Code

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,T,p[100010];char s[100010];int main(){	scanf("%d",&T);	while(T--){		memset(p,0,sizeof(p));		scanf("%s",s+1);		n=strlen(s+1);		for(int i=2,j=0;i<=n;++i){			while(j>0&&s[i]!=s[j+1]) j=p[j];			if(s[i]==s[j+1]) j++;			p[i]=j;		}		int x=n-p[n];		if(x==n) printf("%d\n",n);		else if(n%x==0) puts("0");		else printf("%d\n",x-n%x);	}	return 0;}