mxx的博客

题目链接Codeforces Round 905 (Div.2) Problem A: Chemistry 时间限制: 2秒 内存限制: 256MB 题目描述　　给定一个长度为$n$的仅由小写字母组成的字符串$S$，你需要删除$k$个字符，但是删除哪些字符由你决定，删除完$k$个字符之后剩余的字符你可以随意排列，请问你是否有机会得到一个回文串，即：存在一种删除方案和一种排列方案使得最终的字符串

今天上午花了点时间写了牛客上的一道AC自动机的题，上次看到一篇讲AC自动机的文章之后只是花了些时间先去复习了KMP算法，然后写了KMP的题，AC自动机倒是没试过。不过算法思路大致记得，琢磨了一番终于正确敲出代码了。但是懒得发文章来讲解了，感觉意义不大，想学的人会找到更好的资料，不想学的不会来看的。我就把我的解题代码给贴出来吧。 　　牛客-TJOI2013，我的解法用到的知识点有：AC自动机、

KMP算法介绍　　KMP算法是一种用于在一个源字符串 $S$ 中找目标字符串 $T$ 的所在位置的算法。相较于暴力匹配，它通过对目标字符串 $T$ 的结构进行分析，预先处理得到一些数据，从而能够在匹配过程中跳过大多无用的匹配操作，从而提高查找效率。　　在暴力匹配中，目标字符串与源字符串相应位置匹配不上时，会将匹配的位置后移一位。比如在源字符串 $abcde$ 中试图找到 $cde$ 的位置，会先试