爲什麼我們不這樣改變？

在學習克努特莫里斯普拉特算法一個字符串：爲什麼我們不這樣改變？

ABC ABCDAB ABCDAB

一個模式：

ABCDABD

我被困在一個步驟。我將重點介紹目前我陷入困境的步驟。

ABC ABCDAB ABCDAB 
ABCDABD 

ABC ABCDAB ABCDAB 
    ABCDABD 

ABC ABCDAB ABCDAB 
    ABCDABD 

ABC ABCDAB ABCDAB 
     ABCDABD--------------------(WHY THIS ?)

我不明白上述步驟。我預計上述步驟是：

ABC ABCDAB ABCDAB 
      ABCDABD

請解釋「正確」步驟的邏輯/原因。

來源

2012-11-01 saplingPro

模式中的第二個AB匹配，所以我們轉移，第一個AB現在是第二個AB所在的位置。你爲什麼認爲我們可以進一步轉移？ –

@ n.m。你能告訴我在使用_knuth morris_算法時查找的標準嗎？我完全不理解它，儘管我嘗試閱讀[維基百科文章]（http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm） – saplingPro

當''與'D'比較時發現不匹配。而且這個算法'記住'前面的'AB'是比較的，所以它需要檢查不匹配的字符是否是'C'。

KMP方法的思想在「算法簡介」一書中有解釋。它與無限狀態機方法非常相似，可以幫助你理解它。

來源

2012-11-02 04:12:58 Richard

爲什麼我們不這樣改變？

回答

相關問題