Knuth-Morris-Pratt算法:边界数组

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就设置为borderi+1。

当我试图回答边界数组中的三个连续条目不能与其前一个条目相差一个的问题时，我意识到了缺失的理解。例如border10=3、border11=2、border12=1

为了更好地理解，我希望能有一个好的解释。

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)是一个有趣的问题。