算法题：HDU 4300 Clairewd’s message（拓展KMP）

算法题：HDU 4300 Clairewd’s message（拓展KMP）2014-03-17 csdn博客 shuangde800链接：

http://acm.hdu.edu.cn/showproblem.php？pid=4300

题目大意：

发送一个密文，为字符串S。这段密文的前半部份是加密过的，后半部分是没有加密过的。现在这段密文被截获，但是密文的尾部的一部份损失了。例如，假设密文是xxxxzzzz, xxxx是加密过的，zzzz是没加密的，因为损失了后面一部份，所以截获的内容可能为xxxxzz，可以保证截获的内容的无加密内容一定是完整的。

给出密码表，这个密码表为一串26个字母的字符串，a[0]表示a加密后的字母，a[1]表示b加密后的字母....a[25]表示z加密后的字母。

要你恢复到无损坏的密文。在截获的内容中，要让明文最短。

分析与总结：

先来看看暴力的方法是怎样的。直接从S的一半位置开始枚举，然后判断后面部分的经过加密后是否都和明文部分相匹配即可。

事实证明，数据弱了，可以暴力水过。

如果不水，这题的正解应该是用拓展KMP（资料）

先把S全部都当作是密文的，然后把S全转换成明文，保存为T

这时，S中的密文部分就全部都变成了明文，而明文部分都变成了xxx（不用管是什么）。

然后可以发现，原来的S中的明文部分是S的后缀，而T中的明文部分是T的前缀。

所以，演变成了求S【i....n】中的与T的最长公共前缀，就是赤裸的拓展KMP问题了。