KMP算法(研究總結(jié),字符串)
KMP算法(研究總結(jié),字符串)
前段時(shí)間學(xué)習(xí)KMP算法,感覺(jué)有些復(fù)雜,不過(guò)好歹是弄懂啦,簡(jiǎn)單地記錄一下,方便以后自己回憶。
引入
首先我們來(lái)看一個(gè)例子,現(xiàn)在有兩個(gè)字符串A和B,問(wèn)你在A中是否有B,有幾個(gè)?為了方便敘述,我們先給定兩個(gè)字符串的值
A="abcaabababaa"
B="abab"
那么普通的匹配是怎么操作的呢?
當(dāng)然就是一位一位地比啦。(下面用藍(lán)色表示已經(jīng)匹配,黑色表示匹配失?。?br/>
但是我們發(fā)現(xiàn)這樣匹配很浪費(fèi)!
為什么這么說(shuō)呢,我們看到第4步:
在第4步的時(shí)候,我們發(fā)現(xiàn)第3位上c與a不匹配,然后第五步的時(shí)候我們把B串向后移一位,再?gòu)牡谝粋€(gè)開(kāi)始匹配。
這里就有一個(gè)對(duì)已知信息很大的浪費(fèi),因?yàn)楦鶕?jù)前面的匹配結(jié)果,我們知道B串的前兩位是ab,所以不管怎么移,都是不能和b匹配的,所以應(yīng)該直接跳過(guò)對(duì)A串第二位的匹配,對(duì)于A串的第三位也是同理。
或許這這個(gè)例子還不夠經(jīng)典,我們?cè)倥e一個(gè)。
A="abbaabbbabaa"
B="abbaaba"
在這個(gè)