再次回来总结KMP，发现有点力不从心，学久了，越觉得越来越不理解了。

估计是写KMP已经不下50遍了吧。每次用都是直接默写。。

KMP算法，串模式匹配算法，通过预处理得到next数组，再进行匹配。

几个要重点记忆的地方:

1. next数组的含义 next[i] = t 表示以i位置结尾的前缀串(相对于原串是前缀串)的真前缀和真后缀相等的最大值为t

2. 最小覆盖子串: 我不会证明，但是记得住结论，记len表示字符串的长度，则这个字符串的最小覆盖子串为 len - next[len]

3. KMP的next数组的作用远远超过你的想象。

4. 关于next数组优化的问题，实际过程中有什么必要我至今没有体会到，优化之后next数组的性质反而被破坏。

5. 在匹配的时候，移动的不是next[j], 移动的是j - next[j]个位置

6. 现在详细介绍KMP的文章太多了。。但是 都是在讲表面工作，看个一两篇就行了。

　　推荐一，邓俊辉的数据结构 (我觉得所有我看过的文章和书里面，这本书讲KMP讲得最好，没有之一)

　　推荐二，july的文章(大神很用心，照顾每一个初学者的感受，orz一下，最近居然又重写了。所以我也再总结总结吧。。。)

　　推荐三，算法导论，如果你有心研究，请详细了解时间复杂度的证明等。(网路上的文章基本上都是忽略证明的，显然不够严谨)

这次的总结，不贴代码了，算法这东西真心要多想，少看代码，多思考。。哎

以前总结的时候的代码，请移步 这里

这个总结主要是整理思路

以下练习题来自我在vjudge上开的一个  专题

1.HDU 1711 - Number Sequence  (KMP 模板题)

初学者学完KMP，套用模板可以轻松AC之。

也是新手上路必做的KMP题目

2.HDU 1686 - Oulipo ( KMP 基础题 )

KMP的基础题目，题目大意是给定一个匹配串，再给定一个主串，问给定的匹配串在主串中出现的次数。

注意，这里从题目样例可以看出，各个子串可以有公共部分，也就是说只要在主串中找匹配串就可以，可以重叠

如果你还不理解,看这个样例

AZAAZAZAZA 

AZA在主串中出现了3次，而不是2次。

3.HDU 2087- 剪刀花布 ( KMP 基础题)

这道题唯一要注意的也是上面那题有主意的。

这里是不能重叠的，为什么？剪掉的东西还能再拿回去用吗？显然不行。

如果是按照这题的题意

AZAAZAZAZA 

答案应该是 2 ，为什么，不用再解释了吧。

4.HDU 3746 - Cyclic Nacklace ( next数组运用 )

如果你还在纠结这KMP的模式匹配，那我只能说你还停留在最初级的阶段

因为KMP算法的精髓根本不在匹配上，而是在它的next数组上。

题目大意：给定一个串，问最少在末尾加上多少个字符，能使得原串变为一个循环串，循环节至少为2。

比如 aaa ，已经是循环串了，而且循环次数为 3 故不再需要加字符

再如abca  显然abc是一个循环节，那么再两个字符bc，就变为abcabc，故答案是2

再如abcde 显然abcde是循环节，需要加五个字符

KMP？？怎么用？这个时候就是要用到和循环节有关系的最小循环子串了。

记住 长度为i的字符串，最小循环子串公式为  MinL = i - next[i]

5.HDU 1358 - Period ( next数组性质 )

题目大意：求一个字符串所有前缀的循环节以及对应的循环次数k( k > 1)

例如 aaa  前缀aa 循环节a 循环次数2 前缀aaa 循环节a 循环次数 3

那没显然是对整个串的next数组线性扫描一遍，答案便可以出来。

6.HUST 1010 - The Minimum Length ( next数组性质 )

题目大意：求一个字符串的最小循环子串

这道题目应该放到前面，果断是一道水题

7.POJ 2406 - Power Strings ( next数组性质 )

题目大意：求一个字符串的最小循环子串 的 循环次数

水题。不解释。

8.POJ 2752- Seek the Name, Seek the Fame ( next数组性质

题目大意：给定一个字符串，找出一个子串，要求子串既是原串的前缀，又是原串的后缀

最开始肯定应该从next[len] 开始找，然后再到next[next[len]]找，再找next[next[next[len]]]

想想看，必须是原串的前缀和后缀。找到之后，接下就找被找到的那个子串的子串，再找子串的子串的子串直到没有。

9.POJ 3080 - Blue Jeans ( KMP中档题 )

题目大意：在给定的若干个字符串中，找到最长的公共子串

分析题意和数据范围，枚举第一个字符串的所有子串。然后对其他串进行KMP

10.HDU 2594 -  Simpsons’ Hidden Talents ( KMP中档题 next数组性质

题目大意: 给定两个字符串s1，s2. 找到最长的一个子串ss，要求子串ss即是s1的前缀，又是s2的后缀

很容易想到，直接把s1和s2连起来然后计算next数组。这里可能还会有一个问题。就是如果子串的长度超过了s1或者超过了s2

怎么办，我的处理是在中间再加一个#字符将两个字符串隔开从而避免了这个情况。是从后缀数组的处理学来的

11.HDU 3336 - Count the string ( KMP好题 next数组性质 )

题目大意:给定一个字符串，计算它的所有前缀(包括本身)在原串中出现的次数只和，再%10007

开始天真得以为暴力枚举可以过，果断TLE了两发，后来发现这道题还是用的next数组的性质来做的。

这道题现在没有太深的理解。

12.HDU 4300 - Clairewd’s message (KMP EXKMP)

题意为：给定一个翻译表，即第i个字母用哪个字母表示   

再给一个串，里面前面为密文，后面为明文，密文一定是完整的，但明文不完整或可能没有   

求这个完整的前面密文后面明文的串

果断后来懂得了KMP的做法，EXKMP就算了，先放在一边

做法，把原串s1全部翻译为密文s2，从s2的一半开始找到第一次匹配完成之后j的位置flag。

从flag 到 len - flag 是剩下的要输出的字符的数量。

精华之处在与KMP内部匹配代码的修改。

13.HDU 1238 - Substrings ( KMP 中档题 )

题意：给定若干字符串，求它们的最长公共子串的长度(串可以翻转)

分析题目，看到数据范围很小，果断可以枚举。KMP之。

14.HDU 2328 - Corporate Identity ( KMP中档题

题意：给定若干字符串，求他们的最长公共子串的长度

分析: 简单题

15.HDU 3374 - String Problem ( KMP + 最大最小表示法 好题 )

题意: 给定一个字符串，求它的最大(小)表示法对应的位置，以及在串中出现的次数

分析: 用最大最小表示法求位置，然后用KMP扫两倍的串，扫完再-1.(否则会多算一次)

16.HDU 2609 - How many ( 最小表示法 + set 判重 )

题意：给定若干个字符串，判断有多少个不一样的字符串(字符串可以按照 最小表示法进行变换)

分享: 用最小表示法处理没有个串，然后再加入到set集合中，最好输出集合中的元素数量即可。

17.FZU 1901 - Period Ⅱ ()