记录KMP算法，记录其经典之处

离开学校已经多年了，早已经不再抚弄那些陈旧的书籍。

周末，深圳的天气阴沉，老天这段时间总是很乐意显摆，动不动就给深圳人民来次几十年一遇的暴雨，似乎要把一年的雨水全部在这些天下完似的。

所以呆在家里面看电视，上网，实在也无聊。随手翻开大学时候的（数据结构，还留着啊，当初刚出来的时候总没有底气，总希望能够随时充电用）。看到了字符串的模式匹配一章。突然发现KMP算法是如此的经典。故记之。。。

在提KMP的经典之前，首先要提基本的模式匹配算法：

所谓模式匹配，简单点说就是对两字符串进行匹配，找出一个字符串在另一个字符串中的位置。

基本的模式匹配是这样的：

假设有字符串

S=S1S2......SN（由于为了算法效率的需要，所以一般都把S[0]保存S的长度）

P=P1P2......PM（同上）

其中（M<N），要求返回P在S中出现的位置。

所以算法要点如下：

假设从S中i点开始扫描（也就是从S[i]开始，此时用一个变量k=i），顺序比较S[i]和P[1],S[i+1]和P[2]。这样，当P进行到第j个字符也就是P[j]的时候，发现S[i+j-1]和P[j]不匹配，那么需要把S的指针i回朔到S起始的下一个字符也就是k+1继续比较。

如图：