购物网站开发原理/seo网上培训

题目要求添加几个字符使得原来字符串是循环的。

循环利用NEXT数组的性质，LEN%(LEN-NEXT[LEN])==0，刚好等于0的不需要添加，不等于零的，余数LEN%(LEN-NEXT[LEN])就是多出来的那部分，把余数部分补齐

循环节长度就是LEN-NEXT[LEN]，需要补的就是LEN-NEXT[LEN]-LEN%(LEN-NEXT[LEN]) 

代码

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;#define LEN 100010int nexts[LEN];
char s[LEN];void Getnext(int n)
{int i,j;i=0,j=-1;nexts[0]=-1;while(i<n){if(j==-1 || s[i]==s[j]){i++;j++;nexts[i]=j;}else j=nexts[j];}
}int main()
{int T,len,t,ans;cin>>T;while(T--){scanf("%s",&s);len=strlen(s);Getnext(len);if(len%(len-nexts[len])==0 && nexts[len]!=0) cout<<"0"<<endl;else{t=len-nexts[len];ans=t-len%t;cout<<ans<<endl;}}return 0;
}