话说这道题纠结了两天半,,从周日就开始想的,,就这样一直纠结,纠结,,今天上午终于是ac了,,,,,,题目是让求最少需要增加几个字母,关键是求出字符串的循环节,用kMP算法求循环节,,设字符串长度为len,则循环节长度x=len-next[len-1],由这个公式即可算出来。题目:
Cyclic Nacklace
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 465Accepted Submission(s): 212
Problem Description
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. Being inspired by the entrepreneurial
spirit of "HDU CakeMan", he wants to sell some little things to make money. Of course, this is not an easy task.
As Christmas is around the corner, Boys are busy in choosing christmas presents to send to their girlfriends. It is believed that chain bracelet is a good choice. However, Things are not always so simple, as is known to everyone, girl's fond of the colorful
decoration to make bracelet appears vivid and lively, meanwhile they want to display their mature side as college students. after CC understands the girls demands, he intends to sell the chain bracelet called CharmBracelet. The CharmBracelet is made up with
colorful pearls to show girls' lively, and the most important thing is that it must be connected by a cyclic chain which means the color of pearls are cyclic connected from the left to right. And the cyclic count must be more than one. If you connect the leftmost
pearl and the rightmost pearl of such chain, you can make a CharmBracelet. Just like the pictrue below, this CharmBracelet's cycle is 9 and its cyclic count is 2:
Now CC has brought in some ordinary bracelet chains, he wants to buy minimum number of pearls to make CharmBracelets so that he can save more money. but when remaking the bracelet, he can only add color pearls to the left end and right end of the chain, that
is to say, adding to the middle is forbidden.
CC is satisfied with his ideas and ask you for help.
Input
The first line of the input is a single integer T ( 0 < T <= 100 ) which means the number of test cases.
Each test case contains only one line describe the original ordinary chain to be remade. Each character in the string stands for one pearl and there are 26 kinds of pearls being described by 'a' ~'z' characters. The length of the string Len: ( 3 <= Len <= 100000
).
Output
For each case, you are required to output the minimum count of pearls added to make a CharmBracelet.
Sample Input
Sample Output
ac代码:
分享到:
相关推荐
《字符串模式匹配KMP算法》教学课例设计[归纳].pdf
kmp算法,可匹配字符串中的个别字符。搜索字符
用c++实现kmp算法,进行字符串快速比较,是、使得比较过程移动的距离尽可能短
kmp算法 使用kmp算法文本字符串的模糊匹配_python实现
KMP算法是一个查找两个字符串公共串的算法,比一般的算法效率要高很多.
这是一个关于字符串匹配的kmp算法,程序简单精炼,可以借鉴一下
字符串查找KMP算法
此代码实现了字符串的KMP算法和快速排序算法,能够快速的寻找到制定的字符串
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
KMP算法是字符串匹配最快的一种,效率最高,复杂度最低。时间复杂度也比较低
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...
字符串的模式匹配算法——KMP的C++实现。
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 2、BF算法与KMP算法的区别 3、BF算法为什么要回溯 4、KMP 算法思想 5、next数组的含义 第二部分、next数组求法的来龙去脉与KMP算法的源码
数据结构书上的KMP算法,书上的算法看的不太明白,自己写了一个,有点罗嗦。 也是自己写的,容易看懂
这是字符串匹配算法中很著名的KMP算法,此文件仅供大家参考,具体是否能调通,本人还没有试过
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
@字符串KMP算法c.txt@字符串KMP算法c.txt
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进