文档介绍：中学生文浅谈字符串匹配问题
引言
在程序设计中，经常会出现字符串处理的题目，这一类题目重视选手的创新能力，无论对选手的代码能力异或是思维能力都有着比较高的要求。在此情况下，我们发现了很对处理字符串问题的强有力的工具，例如说KMP算法中学生文浅谈字符串匹配问题
引言
在程序设计中，经常会出现字符串处理的题目，这一类题目重视选手的创新能力，无论对选手的代码能力异或是思维能力都有着比较高的要求。在此情况下，我们发现了很对处理字符串问题的强有力的工具，例如说KMP算法在线性时间内能够得心应手的处理两个字符串之间的匹配问题，后缀数组更是能够通过较低的复杂度处理很多字符串的操作，AC自动机更是可以轻松的处理多串匹配，字符串哈希效率高，编程复杂度低，性价比相当高。当然，具体的应用就该根据情况而定了。
因为同学们对这些算法都很了解，介绍我就不多说了只是浅谈一下对这些算法应用的一些总结。
目录
Kmp算法应用列举
后缀数组的一些应用
AC自动机的应用
字符串哈希的应用
一道例题浅谈比较
Kmp算法应用列举
直接利用next数组求解的：主要是求字符串的循环节、字符串子串与前缀的匹配问题。
直接kmp匹配：这是最基础的，但是因为需要匹配的串的个数可能比较多，因此即使是线性算法，也免不了超时的悲剧。
Kmp+树状数组：poj3167，是一道很经典的kmp好题，即两个字符串的匹配条件为对应的数的在串中排名对应相等。我们在进行kmp匹配的过程中可以时时用树状数组维护当前待匹配字符的排名。
Kmp算法应用小结
Kmp算法的很多应用其实都可以被后缀数组等代替，虽然是线性时间，但是在串数较多的情况下效果也并不是很好。充分了解next指针的一些性质也会有助于解决kmp的题目，poj3167算是我看到过的最好的一道kmp题了，因为这充分利用了kmp两点匹配时的一些特性，通过数据结构顺利地解决了排名问题，这是后缀数组,AC自动机这些常用算法所做不到的。
后缀数组的一些应用
1：给你一个字符串，多次询问某两个后缀的最长公共前缀。
解法：我们可以求得两个后缀的排名，只要通过RMQ求得两个后缀之间的height值的最小值。
2：可重叠的最长重复子串问题。
解法：因为可重叠，因此只需要在height数组中取一个最大值即可。
后缀数组的一些应用
3：不可重叠的最长重复子串问题。
解法：这道题目复杂一点，需要先二分答案，然后问题就变为了判定性问题。即二分重复子串的长度L，那么我们可以将排序后的后缀分为若干份，保证每一份中相邻后缀的最长公共前缀都大于等于L，那我们只需要分别在每组中都操作即可。因为不可重叠，所以每一组我们分别观察位置最靠前和最靠后的后缀，判断它们是否重叠，就可以求出解了。
4：最长回文子串问题。
解法：我们可以先添加要求的字符串S,再将S串翻转一下形成Sˊ，与串S之间加上一个连接将它们连接起来，并求出该串的后缀数组。枚举中心位置的时候，相当于是要求出以枚举的该点为起点的两个后缀的最长公共前缀。
后缀数组的一些应用
5：多个串最长公共子串问题。
解法：因为每一个子串必定是一个后缀的前缀，我们可以依旧将这些串接在一起，相邻两个串之间插入一个分隔符。接下来就简单了，求出了后缀数组之后，我们可以二分子串的长度，然后依据height分为若干段，只要有一段中包含了所以询问串，那么就是可行解了。
6：重复次数最多的连续重复子串问题
解法：我们可以先暴力重复子串的长度L，然后我们可以将这个串分为[1..L],[l+1..2L]…这些块。一个重复次数大于1的串必定包含若干个这样的块，这些块也一定是相等的。那么我们可以枚举起点的一个块，然后得到接下来和它相等的块的个数，再左右调整是否还有被分割下来的匹配块，就可以了。
后缀数组应用小结
后缀数组的应用范围非常广，我只列举了少部分比较经典的。实质上后缀数组在应用过程中不外乎借助于height数组、RMQ算法、二分等辅助算法。在处理多串匹配问题时我们也可以将待匹配的串接在一起。只要我们能够充分了解这些算法的性质，就可以很好的解决这些问题了。
初步想法
这道题目最暴力的方法就是每一个单词都和每一个句子运用kmp匹配，然后统计结果就可以了。复杂度较大，显然过不掉。因为这道题涉及多串匹配，我们考虑使用ac自动机。
Ac自动机
具体做法比较简单，实践也不复杂。显而易见，我们能够将所有单词建立AC自动机，然后对于每一个句子，我们将它在自动机上走一遍，就可以知道一些到达的点，然后将这些到达的点按照fail指针走一遍就可以知道所有可以到达的点，对于每一个经过的点都标记一下。最后结果自然就是查看每一个单词的末尾被多少个句子遍历过。
Ac自动机
本来用fail指针感觉复杂度很高，但又构造不出针对性数据，因