Knuth-Morris-Pratt算法：邊界數組

這是一個用於計算KMP中邊界數組的僞代碼。
p是模式Knuth-Morris-Pratt算法：邊界數組

border[1]:=-1 
i:=border[1] 
for j=2,...,m 
    while i >= 0 and p[i+1] != p[j-1] do i = border[i+1] 
    i++ 
    border[j]:=i

我可以執行以下僞代碼來計算邊界數組，但我現在我遇到的問題是，我真的不明白邊境陣列含義如何解釋它。
例如，如果模式在位置（i + 1）和（j-1）不相等，則變量i被設置爲邊界[i + 1]。爲什麼是這樣的？

當我試圖回答邊界數組中的三個連續條目與前一個條目無法相差的問題時，我意識到缺少的理解。例如。 border [10] = 3，border [11] = 2，border [12] = 1

爲了更好地理解，我將不勝感激。

來源

2017-02-18 tumbler

你稱之爲邊界數組是前綴函數。有很多解釋，請看Stackoverflow,Wikipedia，或者只是google一個更適合你的解釋。

至於你的問題的第二部分，下面的字符串是屬性你問一個例子：

column:
string: abcabac 
border: 0001210

這裏，border[4] = 2因爲ab = ab，border[5] = 1因爲a = a和border[6] = 0。

所有三個值是否可以是非零的（例如，3，2，1）是一個有趣的問題。

來源

2017-02-18 22:26:37 Gassa

其實我GOOGLE了不少，但我無法找到一個解釋，幫助一個更好的瞭解。我發現的所有解釋都是解釋算法是如何進行的，而不是它背後的想法。 – tumbler

@ t I我實際上向學生解釋了很多次使用不同方法的KMP。通常會有一個學生說：「嘿，這次我聽到了第四個解釋，現在它非常有意義！」。然而，大多數人會喜歡「嗯，我明白......總的來說......」。所以，我不知道通用的解釋KMP的方法;在我的經驗，瞭解它要求聽證 - 或讀 - 幾個不同的解釋，直到你的這些「點擊」一個（但也許不是爲別人）。 – Gassa

Knuth-Morris-Pratt算法：邊界數組

回答

相關問題