[HDU3746]Cyclic Nacklace(KMP)

发布于 2018-02-22  147 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU3746]Cyclic Nacklace(KMP)

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.

Http

HDU

Tag

KMP

题目大意

给出一个串,求在这个串的两侧添加最少的字符使得它成为一个完整的循环串。

解决思路

首先知道,在串的两边加字符与只在一边加效果是一样的,因为是循环串,那么问题转化为在一个字符串后面加上若干个字符使得整个字符串成为一个循环串。
那么先来看这个循环串需要满足的条件,它的循环节的前缀一定是整个原字符串的后缀,因为可以将原字符串看作若干个循环节后面接上一个不完整的循环节的前缀。所以可以从最后一个字符开始跳\(Next\),这样就可以标记出所有包含原串后缀的所有前缀,即能匹配上。
然后我们从前往后枚举循环节的长度。首先判断是不是真的是循环的。由于已经知道了长度,那么我们就可以求出这个循环节完整的最后一次结束的位置,假设这个位置是\(pos\),当前循环节的长度为\(i\),那么若\(\frac{pos}{pos-Next[pos]}\)为整数并且\(pos-Next[pos]==i\),则这个循环节是合法的(证明可以参考这里)。接着判断剩下的\(n-pos\)位是否能构成合法一个残缺的循环节(即剩下的\(n-pos\)位能匹配循环节的前\(n-pos\)位),这个直接看原串的第\(n-pos\)位在我们的第一步中是否被标记即可。最后需要注意的是,当枚举循环节长度枚举到最后一位时,要特殊判断整个原串是否本身就是循环的,此时答案为\(0\)。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU3746]Cyclic Nacklace(KMP)


HNCJ OIer