InTheBloodHorse

每日一题(52) hud3746

字数统计: 244阅读时长: 1 min
2019/01/17 Share

题目地址

题意

问给的字符串后面还要拼接几个字母才可以使字符串是循环的

思路

利用KMP的前后缀思路,找出最长串的前缀,后缀交集最长元素的长度。

  1. 长度为0,说明没有交集,长度为拼接长度为原字符串
  2. (原长度) -(最大长度) 能被 (最大长度)乘除,说明已经循环
  3. 无法整除,则补上相应的位数。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int nextval[100005];
char s[100005];
void gen_next(){
int ll = strlen(s);
nextval[0]=0;
nextval[1]=0;
int k=0;
for(int i=1;i<ll;i++){
while(k>0 && s[k]!=s[i]) k = nextval[k];
if(s[k]==s[i]) k++;
nextval[i+1]=k;
}
nextval[0]=-1;
}


int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(nextval,0,sizeof(nextval));
scanf("%s",s);
int ll = strlen(s);
gen_next();
int number = ll - nextval[ll];
if(number==ll) printf("%d\n",number);
else if(ll % number ==0) printf("0\n");
else printf("%d\n",number - ll % number);
}
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2019/01/17/每日一题-52-hud3746/

发表日期:January 17th 2019, 10:51:05 pm

更新日期:January 17th 2019, 11:01:21 pm

版权声明:Have a fun

CATALOG
  1. 1. 题意
  2. 2. 思路