導航:首頁 > 源碼編譯 > 集合快速匹配字元串演算法

集合快速匹配字元串演算法

發布時間:2024-11-11 16:56:41

① 圖解KMP字元串匹配演算法

kmp演算法跟之前講的bm演算法思想有一定的相似性。之前提到過,bm演算法中有個好後綴的概念,而在kmp中有個好前綴的概念,什麼是好前綴,我們先來看下面這個例子。

觀察上面這個例子,已經匹配的abcde稱為好前綴,a與之後的bcde都不匹配,所以沒有必要再比一次,直接滑動到e之後即可。
  那如果前綴中有互相匹配的字元呢?

觀察上面這個例子,這個時候如果我們直接滑到好前綴之後,則會過度滑動,錯失匹配子串。那我們如何根據好前綴來進行合理滑動?

  其實就是看當前的好前綴的前綴和後綴是否有匹配的,找到最長匹配長度,直接滑動。鑒於不止一次找最長匹配長度,我們完全可以先初始化一個數組,保存在當前好前綴情況下,最長匹配長度是多少,這時候我們的next數組就出來了。

  我們定義一個next數組,表示在當前好前綴下,好前綴的前綴和後綴的最長匹配子串長度,這個最長匹配長度表示這個子串之前已經匹配過匹配了,不需要再次進行匹配,直接從子串的下一個字元開始匹配。

 我們是否每次算next[i]時都需要每一個字元進行匹配,是否可以根據next[i - 1]進行推導以便減少不必要的比較。
  帶著這個思路我們來看看下面的步驟:
  假設next[i - 1] = k - 1;
  如果modelStr[k] = modelStr[i] 則next[i]=k

如果modelStr[k] != modelStr[i],我們是否可以直接認定next[i] = next[i - 1]?

通過上面這個例子,我們可以很清晰地看到,next[i]!=next[i-1],那當modelStr[k]!=modelStr[i]時候,我們已知next[0],next[1]…next[i-1],如何推導出next[i]呢?
  假設modelStr[x…i]是前綴後綴能匹配的最長後綴子串,那麼最長匹配前綴子串為modelStr[0…i-x]

我們在求這個最長匹配串的時候,他的前面的次長匹配串(不包含當前i的),也就是modelStr[x…i-1]在之前應該是已經求解出來了的,因此我們只需要找到這個某一個已經求解的匹配串,假設前綴子串為modelStr[0…i-x-1],後綴子串為modelStr[x…i-1],且modelStr[i-x] == modelStr[i],這個前綴後綴子串即為次前綴子串,加上當前字元即為最長匹配前綴後綴子串。
代碼實現
  首先在kmp演算法中最主要的next數組,這個數組標志著截止到當前下標的最長前綴後綴匹配子串字元個數,kmp演算法裡面,如果某個前綴是好前綴,即與模式串前綴匹配,我們就可以利用一定的技巧不止向前滑動一個字元,具體看前面的講解。我們提前不知道哪些是好前綴,並且匹配過程不止一次,因此我們在最開始調用一個初始化方法,初始化next數組。
  1.如果上一個字元的最長前綴子串的下一個字元==當前字元,上一個字元的最長前綴子串直接加上當前字元即可
  2.如果不等於,需要找到之前存在的最長前綴子串的下一個字元等於當前子串的,然後設置當前字元子串的最長前綴後綴子串

然後開始利用next數組進行匹配,從第一個字元開始匹配進行匹配,找到第一個不匹配的字元,這時候之前的都是匹配的,接下來先判斷是否已經是完全匹配,是直接返回,不是,判斷是否第一個就不匹配,是直接往後面匹配。如果有好前綴,這時候就利用到了next數組,通過next數組知道當前可以從哪個開始匹配,之前的都不用進行匹配。

閱讀全文

與集合快速匹配字元串演算法相關的資料

熱點內容
有什麼測身高的app安卓 瀏覽:364
通過買東西來解壓 瀏覽:338
游戲運行文件解壓到哪個盤 瀏覽:119
銀行業務程序員要注意什麼 瀏覽:390
怎麼看壓縮機牌子的 瀏覽:900
安卓手機怎麼設置網址黑名 瀏覽:311
女超人全在哪個App可以看 瀏覽:393
可樂優品app圖標長什麼樣子 瀏覽:870
iphone米家app怎麼掃碼 瀏覽:575
servqual具體演算法 瀏覽:287
怎麼在app關閉閃付 瀏覽:456
一個壓縮文件能解壓多久 瀏覽:573
如何在光遇中知道自己被拉黑安卓 瀏覽:664
c跨平台開發技術指南pdf 瀏覽:546
演算法分析師就業人數圖 瀏覽:820
安卓手機相冊為什麼看不到照片 瀏覽:328
linux如何更新python版本 瀏覽:359
pdf文件打馬賽克 瀏覽:60
模板提高編譯速度 瀏覽:146
ppt硬核訓練營解壓密碼 瀏覽:584