Cyclic Nacklace HDU - 3746
阅读原文时间:2023年07月12日阅读:3

CC这个月底总是很郁闷,昨天他查了他的信用卡,没有任何意外,只剩下99.9元了。他很苦恼,想着如何度过这最后的几天。受“HDU CakeMan”企业家精神的启发,他想卖一些小东西来赚钱。当然,这并非易事。圣诞节就要到了,男孩们都忙着挑选圣诞礼物送给女朋友。人们认为,链手镯是一个很好的选择。然而,事情并不总是那么简单,众所周知,女孩喜欢用五颜六色的装饰来使手镯显得生动活泼,同时她们也想展示自己作为大学生成熟的一面。CC了解了女孩们的需求后,打算出售这款名为CharmBracelet的chain bracelet。这个CharmBracelet是由五颜六色的珍珠组成的,为了展现女孩的活泼,最重要的是它必须有一个环链连接,这意味着珍珠的颜色是从左到右的环链连接的。循环计数必须大于1。如果你把这条链子最左边的珍珠和最右边的珍珠连接起来,你就可以做成一个迷人的手镯。如下图所示,这个CharmBracelet的cycle是9,cycle count是2:现在CC带来了一些普通的手链,他想买最少数量的珍珠来做charmbracelet,这样他可以节省更多的钱。但是在重新制作手链的时候,他只能在链的左端和右端添加彩色珍珠,也就是说,中间添加是禁止的。CC对他的想法很满意,请您帮助。

输入输入的第一行是单个整数T (0 < T <= 100),表示测试用例的数量。每个测试用例只包含一行描述要重做的原始普通链。字符串中的每个字符代表一颗珍珠,共有26种珍珠由“a”~“z”字符描述。字符串长度Len:(3 <= Len <= 100000)。

输出每一个箱子,你被要求输出的最低数量的珍珠添加到一个CharmBracelet。

样例输入

3
aaa
abca
abcde

Sample Output

0
2
5

题意:

就是给你一个字符串,让你是这个字符串变成一个至少有两个循环节的字符串,问至少添加几个字符可以达到这样的目的

添加字符只能在头部和尾部添加不能在中间添加(这是个环)

题解:

KMP最小循环节、循环周期:

定理:假设S的长度为len,则S存在最小循环节,循环节的长度L为len-next[len],子串为S[0…len-next[len]-1]。

(1)如果len可以被len - next[len]整除,则表明字符串S可以完全由循环节循环组成,循环周期T=len/L。

(2)如果不能,说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L,L=len-next[len]。

证明看这里--------->    点击

知道定理了那么这道题也就不难了

代码:

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 const int maxn=100005;
7 const int INF=0x3f3f3f3f;
8 char ptr[maxn];
9 void get_next(int len,int *next)
10 {
11 next[0]=-1;
12 int k=-1;
13 for(int i=1;i<=len-1;++i) 14 { 15 while(k>-1 && ptr[k+1]!=ptr[i])
16 k=next[k];
17 if(ptr[k+1]==ptr[i])
18 {
19 k+=1;
20 }
21 next[i]=k;
22 }
23 }
24 int main()
25 {
26 int t;
27 scanf("%d",&t);
28 while(t--)
29 {
30 scanf("%s",ptr);
31 int len=strlen(ptr);
32 int next[len];
33 get_next(len,next);
34 int length=len-(next[len-1]+1);
35 if(len != length && len%length == 0)
36 {
37 printf("0\n");
38 }
39 else
40 {
41 int add=length-(next[len-1]+1)%length;
42 printf("%d\n",add);
43 }
44 }
45 return 0;
46 }

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章