2011-07-09 95 views
4

我正在讀的理論&數據結構的問題(西摩Lipschuz)。這是什麼模式匹配算法?

讓我提供一個我正在閱讀的部分的圖像。 link of this book

本書的這一部分講述了一種名爲「第二模式匹配算法」的模式匹配算法。

這是什麼算法?這是Boyer-Moore還是KMP或Horspool?還是什麼?

或者,這是作者生產的任何新算法?

+3

我們應該如何在沒有書的情況下回答這個問題? –

+1

沒錯,所以我們知道這本書的標題,但是如何幫助識別書中的算法呢?你認爲所有程序員都擁有一份副本嗎? –

+0

我點擊了鏈接,它只是書的封面和鏈接購買它。 [這裏是截圖](http://i.imgur.com/hTlwC.png)。 –

回答

4

我相信這是KMP算法。 KMP構造了一個「失敗表」,它本質上是一個自動機,說「如果你對特定字符不匹配,你還能匹配多少模式字符串?」它也對模式進行預處理,而不是匹配的字符串。此外,如果您看一下Aho-Corasick算法(這是KMP的泛化),則會構建此自動機的更通用版本,該版本可以一次處理多個模式。因此,我非常肯定你在看KMP。