string - Knuth–Morris–Pratt algorithm: border array

Question

Here is a pseudo code for computing the border array in KMP.
p is the pattern

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 can execute the following pseudo code to compute the border array but the problem I am having right now is that I don't really understand the border array meaning how to interpret it.
For instance if the pattern does not equal at position (i+1) and (j-1) the variable i is set to border[i+1]. Why is that for example?

I realized the missing understanding when I tried to answer the question that three consecutive entries in a border array cannot differ by one from its predecessor. E.g. border[10]=3, border[11]=2, border[12]=1

I would appreciate a good explanation in order to get a better understanding.

Answer 1

你所说的边框数组就是前缀函数。有很多解释，请参阅Stackoverflow、Wikipedia，或者只是google一个更适合您的解释。

至于您问题的第二部分，以下字符串是您要求的属性的示例：

column:  0123456
string:  abcabac
border:  0001210

在这里，border[4] = 2因为ab = ab，border[5] = 1因为a = a，和border[6] = 0。

是否所有三个值都可以为非零（例如，3、2、1）是一个有趣的问题。