KMP算法（研究總結(jié)，字符串）

KMP算法（研究總結(jié)，字符串）

前段時間學(xué)習(xí)KMP算法，感覺有些復(fù)雜，不過好歹是弄懂啦，簡單地記錄一下，方便以后自己回憶。

引入

首先我們來看一個例子，現(xiàn)在有兩個字符串A和B，問你在A中是否有B，有幾個？為了方便敘述，我們先給定兩個字符串的值
A="abcaabababaa"
B="abab"
那么普通的匹配是怎么操作的呢？
當(dāng)然就是一位一位地比啦。（下面用藍(lán)色表示已經(jīng)匹配，黑色表示匹配失?。?br/>移動開發(fā)培訓(xùn),Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),手機(jī)維修培訓(xùn),手機(jī)軟件培訓(xùn)
但是我們發(fā)現(xiàn)這樣匹配很浪費!
為什么這么說呢，我們看到第4步：
移動開發(fā)培訓(xùn),Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),手機(jī)維修培訓(xùn),手機(jī)軟件培訓(xùn)
在第4步的時候，我們發(fā)現(xiàn)第3位上c與a不匹配，然后第五步的時候我們把B串向后移一位，再從第一個開始匹配。
移動開發(fā)培訓(xùn),Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),手機(jī)維修培訓(xùn),手機(jī)軟件培訓(xùn)
這里就有一個對已知信息很大的浪費，因為根據(jù)前面的匹配結(jié)果，我們知道B串的前兩位是ab，所以不管怎么移，都是不能和b匹配的,所以應(yīng)該直接跳過對A串第二位的匹配，對于A串的第三位也是同理。

或許這這個例子還不夠經(jīng)典，我們再舉一個。

A="abbaabbbabaa"
B="abbaaba"

在這個