转载请加上：http://www.cnblogs.com/courtier/p/4273193.html
1：首先，在阅读此篇文章之前，你至少要了解过，什么是有限状态机，什么是KMP算法，因为，本文是从KMP的源头，有限状态
机来讲起的，因为，KMP就是DFA（Deterministic Finite Automaton)上简化的。
2：很多KMP的文章（有限自动机去解释的很少），写得在我看来不够好，你如果，没有良好的数学基础就很难去理解他们（比如下图），
因为，你能够理解KMP算法就已经可以入ACM新手的大门了，有很多人说一个算法就能进入ACM？来我们看看为什么叫KMP算法，很简单
这个是由三个数学家发明的，那么，我说一个算法要由三个数学家来推理，就可以说明这个分量的了。
3：有些人问，我能够举例出Next的方法来做这类题呀，我感觉太喽了，特别是计算机专业的，KMP算法还用数组慢慢移给别人看？
假设，你是面试官你是收慢慢移动的人呢？还是给出DFA的人呢？我们开始正题吧，废话有点多
( 算法导论 )
就是画出下图的有限自动机，
(帅吧，简直就是酷逼了，字符串能画成这么帅)
1.首先，画好状态图，以上图为例，我们的输入
= {A,B,C}(因为，我们模式串只有ABC三位)，构造出如下图:
2.根据上图，建立下面一张表:（就是0输入a到1等这类关系矩阵）:
| 0 | 1 | 2 | 3 | 4 | 5 | |
| A | B | A | B | A | C | |
| A | 1 | 3 | 5 | |||
| B | 2 | 4 | ||||
| C | 6 |
3.在上面我们设置了一个X（这个是关键中的关键了）我们来看看怎么用？
1. 这两个X=0怎么来的呢？第一个，不用看，一定是0。第二个，我们就要看
当前的列所代表的字母（就是列的第一个字母）跟前面的X的值所在的列中与当前字母相同的就
是X的值（比如，第1列的字母是B，前面一个的X是0，So，看第0列的”B ”是0），所以，第0
列的B的值赋值给当前列，即X=0
2. 再把前一个X所代表的列赋值给当前列。进入下一个。
Example 1
| X=0 | X=0 | |||||
| 0 | 1 | 2 | 3 | 4 | 5 | |
| A | B | A | B | A | C | |
|
A |
1 |
1 |
3 |
|
5 |
|
|
B |
0 |
2 |
|
4 |
|
|
|
C |
0 |
0 |
|
|
|
6 |
Example 2
| X=0 | X=0 | X=1 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | |
| A | B | A | B | A | C | |
| A | 1 | 1 | 3 | 5 | ||
| B | 0 | 2 | 0 | 4 | ||
| C | 0 | 0 | 0 | 6 |
4. 整张表如下：
| X=0 | X=0 | X=1 | X=2 | X=3 | X=0 | |
| 0 | 1 | 2 | 3 | 4 | 5 | |
| A | B | A | B | A | C | |
| A | 1 | 1 | 3 | 1 | 5 | 1 |
| B | 0 | 2 | 0 | 4 | 0 | 4 |
| C | 0 | 0 | 0 | 0 | 0 | 6 |
https://github.com/aliencool/Algorithm/tree/master/Searching
为什么很多人叫KMP算法叫”看毛片“算法，就因为是拼音？太LOW了这样子解释，为什么呢？因为，KMP他不回溯，每次，都是
模式串自己搞自己（你懂的），所以，才叫”看毛片“算法。
如果，你还有问题或者其他，请给我联系，请期待我下一篇可能是关于倒排索引或者基础理论的算法或者代码，谢谢，O(∩_∩)O!
从有限状态机的角度去理解Knuth-Morris-Pratt Algorithm(又叫KMP算法，”看毛片“算法)
原文：http://www.cnblogs.com/courtier/p/4273193.html