原题是英文,咱们按咱们的翻译来哈
有一个字符序列，现在问你:
序列后面最少补充几个元素使其恰能成为几个重复循环的序列。
Input
第一行是一个整数 T ( 0 < T <= 100 ) 代表测试数据的组数.
之后T行每行一个字符串. 由小写字母'a'-'z'组成. 字符串的长度为: ( 3 <= Len <= 100000 ).
Output
对于每组测试数据，输出一行,即序列后面最少补充几个元素使其恰能成为几个重复循环的序列。
输入样例
3
aaa
abca
abcde
输出样例
0
2
5
Hind
最小循环节（len / (len-next[len])）
此题妙就妙在有hint(不是hind233333)
我们看图中第一组样例
循环节:4
需要补充:2
然后暗示中公式:6-2=4;
再看第二组:
循环节:2
需要补充:0;
看出来没有啊~
没有的话我补一组
位置 0 1 2 3 4 5 6 7 8 9 10 11 12
内容 A B A B C A B A B C A B &
next-1 0 0 1 2 0 1 2 3 4 5 6 7
然后按照刚才的算式:12-7=5
我们可以发现12就是数组长度len,7就是next[len]的结果,算出来的5呢 就是循环节的长度
那么需要补充循环节怎么算呢
自然就是字符组长度对循环节长度取余咯
那么就有一个问题 该怎么实现呢
首先我们需要计算next
这个直接模板
//为了方便直接定义全局数组,但是记得初始化什么的
string s2;//这个定义在里面经过某人实践会wa 你懂的
int netx[100100];
int len;
void wnetx(){int i=0,j=-1; netx[0]=-1; while(i<len){ if(j==-1||s2[i]==s2[j]){ i++; j++; netx[i]=j; } else j=netx[j]; }
}今儿上课讲过了 不在多言
然后就是对于情况的判定了
首先计算循环节的长度
int num=len-netx[len];需要补充的字符长度是
ans=num-len%num;这里的话我们需要考虑一种情况
假设有一个字符串11111
他的循环节长度是1
我们根据上面的公式计算他需要补充的字符长度是0
但是还有一种情况
假设有一个字符串是12345
他的循环节长度是5
同样,根据上述公式我们计算得到的也是0
那既然这样的话我们就需要特判一下这种情况
可以观察出,第二种情况数组长度和循环节长度相同
所以我们可以这么写
if(len/num==1)cout<<len<<endl;
elsecout<<"0"<<endl;然后剩下的情况就是特别正常的情况咯
完全代码如下:
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<set>
// #define Kongxiangzhouye
#define sd(x) scanf("%d",&x)
#define ss(x) scanf("%s",x)
#define sc(x) scanf("%c",&x)
#define sf(x) scanf("%f",&x)
#define slf(x) scanf("%lf",&x)
#define slld(x) scanf("%lld",&x)
#define me(x,b) memset(x,b,sizeof(x))
#define pd(d) printf("%d\n",d);
#define plld(d) printf("%lld\n",d)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=100000;
const int INF = 0x3f3f3f3f;string s2;
int netx[100100];
int len;
void wnetx(){int i=0,j=-1; netx[0]=-1; while(i<len){ if(j==-1||s2[i]==s2[j]){ i++; j++; netx[i]=j; } else j=netx[j]; }
}
int main()
{#ifdef Kongxiangzhouyefreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifios::sync_with_stdio(false);int n;cin>>n;while(n--){cin>>s2;len=s2.length();wnetx();int num=len-netx[len];if(len%num==0)if(len/num==1)cout<<len<<endl;elsecout<<"0"<<endl;elsecout<<num-len%num<<endl;} return 0;
}