什么是KMP算法?
快速地從一個主串中找出一個相同的字串
黃色的叫模式串
藍(lán)色的叫主串
快速地從上面的主串中找出一段與之相同的字串
注意強調(diào) 快速地
可以發(fā)現(xiàn):
①箭頭左邊地部分 上下 模式串和主串 完全匹配
②模式串左右兩端 有兩個子串 它們是完全匹配的
左右兩端都有AB子串 它們兩個稱為模式串的 公共前后綴
KMP核心:
直接移動模式串,使得其公共前后綴里 原先的前綴 直接移動到 后綴原先的位置
這樣移動可以保證 當(dāng)前比較指針 所在的位置 它左邊的串 上下是匹配的
為什么呢?
因為公共前后綴是匹配的 移動之前指針左邊的串上下是匹配的
所以把前綴移到后綴的位置 上下也是匹配的
?標(biāo)識的那個位置字符 與 主串 不匹配
這個時候 只需要找到?之前的串 當(dāng)中的 公共前后綴 , 然后往前移動 模式串 使得前綴 來到原來 后綴的位置
如果模式串中 有多對公共前后綴 , 要取最長的一對
找公共前后綴
只有這一對 且是最長的
發(fā)現(xiàn)模式串 已經(jīng) 超過主串的范圍了
判定 匹配失敗 ,主串中不含有和 模式串 相同的 子串
找公共前后綴 : 找最長的 且長度要小于 比較指針左端長度的公共前后綴
在這個移動過程中 根本就不需要看主串
KMP算法
只研究模式串就夠了
把模式串相關(guān)信息挖掘出來之后,用它就可以和任何 主串 進行匹配
注意: 模式串是從 數(shù)組下標(biāo)1 開始存儲的 0位置什么都沒有存
當(dāng)然也可以從數(shù)組下標(biāo)0開始存(原理一樣 , 只是 結(jié)果值相差一個位置)
這部分從1開始存的學(xué)校比較多
就采取了這種大多數(shù)人比較習(xí)慣的方式
假設(shè)可以和任何主串進行KMP算法,每一個位置都可能發(fā)生不匹配
假如第一個位置就發(fā)生不匹配,
假設(shè)第二個位置發(fā)生不匹配,
箭頭左邊的子串長度只有1
公共前后綴的長度要求小于子串的長度
那么公共前后綴的長度只能為0
類比公共前后綴不為0的情況
移動之后指針左邊的長度 就是公共前后綴的長度
這里呢公共前后綴長度是0,移動之后落在模式串中指針左邊的子串就為0
比較指針?biāo)傅奈恢?就是主串中發(fā)生不匹配的位置 我們叫它 當(dāng)前位置
這種情況下: 拿模式串的1號位 與 主串中 當(dāng)前位置進行比較
next數(shù)組 (下一步數(shù)組)
這個數(shù)組 指示了 如果發(fā)生不匹配時下一步該干什么
