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算法：边界数组

回答

相关问题