Tag Archives: kmp

Codeforces #7 Problem D Palindrome Degree

题目描述:

定义k-回文串如下:(1)任何串(包括空串)都是0-回文; (2)一个长度为n的回文串,若它的前n/2个字符和后n/2个字符都是(k-1)-回文,则它是k-回文。现给定一个串(长度不超过5,000,000),设它的每个前缀分别是x-回文,求所有这些x值的和。比如abacaba,其中”a”是1-回文,”aba”是2-回文,”abacaba”是3-回文,故输出6。

题解:

其实这题完全应该在比赛时做出来,因为我见过类似的处理方法。结果我读错题了,以为只有空串才是0-回文,然后就悲剧了。

我的做法是这样的,把原串翻转后拼接在原来的串后面,用一个不在字母表中的分隔符隔开的。然后用KMP里对模式串的预处理那个过程,求出失配以后往前跳的那个指针。我们从新串最后一个位置开始,每向前跳一次都得到一个回文前缀。比如有这样一个串 abaaba…..(后面部分省略),拼接后得到

abaaba......#......abaaba
012345......#......6789AB

则最后位置的失配指针为5,由KMP的意义,也就是说(012345) == (6789AB),而同时由我们的翻转操作知(012345)==(BA9876),故(012345)为一个回文串。从5继续向前跳到2,同理(012)也是回文串。

由上过程可以把全部回文前缀作好标记。然后再从左到右简单地扫描一遍就可以把每个k值计算出来了。

ps. Petr的速度简直匪夷所思……