我在使用 Knuth-Morris-Pratt 找到模式 P = abacaaba 的正确故障链接时遇到问题。
这是我到目前为止所得到的：
k 1 2 3 4 5 6 7 8
P(k) 蕉麻
FLink(k) 0 0 1 0 1 1 1 1
- 第一个始终为 0
- 现在我们有 k(i) = a1 和 k(j) = b2，这些是不匹配的，所以它应该是 0
- 现在我们有 k(i) = a1 和 k(j) = a3，它们是匹配的，a1 = 0，所以 a3 = 0 + 1 = 1
- 现在我们将 i 和 j 向右跳一个，k(i) = b2 和 k(j) = c4，这些是不匹配的，所以我们将 i 跳回 1。现在 k(i) = a1，这是一个不匹配。我们不能再回去了，所以 c4 = 0
- 现在 k(i) = a1 和 k(j) = a5，它们是匹配的。a1 的值为 0，所以 a5 = 0 + 1 = 1。
- 我们再次将 i 和 j 放在右边。k(i) = b2 和 k(j) = a6。这是一个不匹配。我们将 i 放回 1，所以 k(i) = a1。a1 和 a6 匹配，a1 的值为 0，所以 a6 = 0 + 1 = 1。
- 我们再次将 i 和 j 放在右边。k(i) = b2 和 k(j) = b7。这些是匹配的，b2 的值为 0，因此 b7 的值为 0 + 1 = 1。
- 最后 k(i) = b2 和 k(j) = a8。这些不匹配，新的 k(i) 将是 a1。a1 和 a8 匹配，i 的值为 0，所以 a8 = 0 + 1 = 1。
我的老师给 FLink(k) 的答案是 0 1 1 2 1 2 2 3。我做错了什么吗？