Knuth-Morris-Prattアルゴリズム：border array

Question

ここは、KMPの境界配列を計算するための疑似コードです。
pは、私はボーダー配列を計算するために、以下の擬似コードを実行することができますが、私は今が午前問題は、私は本当にそれをどのように解釈するかを意味ボーダー配列を理解していないということであるパターン

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]に設定されます。それはどうしてですか？

境界配列の3つの連続したエントリが前のものと異なることはできないという質問に答えようとしたとき、私は理解が失われていることに気付きました。例えば。国境[10] = 3、国境[11] = 2、国境[12] = 1

わかりやすい説明をいただければ幸いです。

Answer 1

境界配列と呼ばれるのは接頭辞機能です。 多くの説明があります。Stackoverflow,Wikipedia、またはgoogleという説明があります。

column:
string: abcabac 
border: 0001210 

ここ

、border[4] = 2、ab = abためborder[5] = 1ためa = a、およびborder[6] = 0：あなたの質問の後半部分については

は、次の文字列は、あなたが求めるプロパティの例です。

3つの値がすべてゼロ以外（たとえば、3,2,1）になるかどうかは興味深い質問です。