有限自動機字符串匹配器

Question

我想建立一個使用java的字符串匹配器。我有以下僞代碼。

對於有限自動機-匹配器算法來工作的過渡函數必須被計算。以下算法計算轉換函數計算給定模式P和字母σ。

在上面的代碼我無法理解哪兒來分鐘（M + 1，Q + 2）來自。 （我明白爲什麼它是k = min（m + 1，q + 2）而不是k = min（m，q + 1），但爲什麼我們希望m和q + 1的最小值在第一位）

在5-7行之間它將k減1，直到Pk是Pqa的後綴，但我不明白Pqa代表什麼。

另外，如何將第8行轉換爲java代碼？二維數組是否足夠了？還是我需要另一個數據結構？

一個相關的問題：string matching with finite automata

Answer 1

在內部重複，直到環說，我們有PQ =「abdab」和字符串爲「abdabcd」，和我們的拼音是ABCD，我們正在尋找每一個最好的選擇從字母表中的符號，然後存儲轉換到新的狀態。在上面的情況下，'a'應該移動到開始，'b'開始，c延長匹配，並且d符號應該在我們的初始字符串中存儲指向第三個符號的指針。所以Pqa應該被認爲是Pq加字母a的字母。

編輯爲什麼我們希望min（q + 2和m + 1），因爲我們想向前邁進一步，而且我們也想限制字符串的長度，這很明顯。爲什麼我們不能執行q + 3，+ 4？這是因爲我們只添加了一個字符，並且不可能通過一個字符擴展從q到q + 2，+ 3的最佳匹配。