熱身
從 bbabbcbbabbe這串字符串中
找出bbabbe
BF算法：
無腦窮舉，暴力匹配愕掏。其核心思想是匹配串（簡稱S串）和目標(biāo)串（簡稱T串）從第一位開始逐一匹配嚷量。當(dāng)某位匹配失敗，則S串整體向右移一位，繼續(xù)和T串匹配惶翻。以此類推。每次匹配失敗鹅心，則移動一格吕粗，繼續(xù)尋找。這其實是一種窮舉法旭愧，雖然可以解決問題颅筋，但是效率低下。
KMP算法：
可以把它理解為BF的改良版输枯，通過觀察S串的自身特點议泵，不再一格一格的移動，而是跳躍移動桃熄，避免了BF的很多無效匹配先口，從而大大提升了效率。既然是跳躍瞳收，那就有兩個無法回避的問題：
1.每次跳的盡可能多（保證效率）碉京。
2.不能瞎跳的太多，導(dǎo)致錯過了匹配（保證正確性）螟深。
所以到底應(yīng)該怎么跳谐宙？
首先，我們來看一看熱身的例子界弧，T1=S1凡蜻，T2=S2搭综，T3=S3，T4=S4划栓，T5=S5设凹，
T6 = c，S6 = e茅姜。所以在第六位的時候匹配失敗闪朱。根據(jù)前文的介紹，下面一步我們會對S串向右進(jìn)行移動钻洒。那么移動多少格呢奋姿？理論上來說最少移動一格，最多移動五格（因為在第六位失敗素标，極限也就是用S1去和T6比）称诗。
如果移動1格，那就是BF算法头遭，效率太慢（有的時候寓免，確實只能移動一格）。
如果移動5格计维，會不會存在跳過了匹配項的情況袜香？
所以為了知道到底移動多少，我們需要對S1-S5（bbabb）再做一次匹配鲫惶。
既然前面5位匹配成功了蜈首，那么T串的前五位肯定和S串的前五位相同。所以說S串在這段范圍內(nèi)去匹配T串欠母，相當(dāng)于自己的頭去匹配自己的尾巴欢策，這個匹配成功后形成的錯位也就是S串最終跳躍的距離。也就相當(dāng)于用這個頭部的后面一位S3去匹配去匹配失敗位T6赏淌。
所以我們得出結(jié)論當(dāng)S6匹配失敗了，就用S3去匹配T串的失敗位六水，我們把這個3記錄到S6下面俺孙。以后每當(dāng)S6匹配失敗，我們就用S3去和T串的失敗位對齊匹配缩擂。如果S串的每一位下面鼠冕，我們都計算得出一個數(shù)值。我們是不是就相當(dāng)于得到了一個跳躍說明書（next數(shù)組胯盯，也稱K數(shù)組）懈费？答案：是的。
結(jié)論
KMP算法的核心就是避免BF的不必要回溯博脑，問題由匹配串決定憎乙，而不是目標(biāo)串票罐。通過總結(jié)K數(shù)組，當(dāng)某位不匹配的時候泞边，用k數(shù)組記錄的下標(biāo)位（匹配串）去匹配（目標(biāo)串）匹配失敗的那一位该押。
由于本節(jié)主要是為了闡述KMP算法的思想，所以沒有引入代碼阵谚，有興趣的同學(xué)可以在網(wǎng)上查找相關(guān)代碼蚕礼，加深理解。
