kmp算法如何处理这样的错误？

Question

我得到算法这里

但是对于具有重复模式的算法来说，另一个字符串会是什么？

即 字符串：

a b c b b c b d a b c b d

图案：

a b c b d

lp：

0 0 0 2 0

在

j=4 i=4

处给出不匹配

下一个：

j=2 i=5 match (b)
j=3 i=6 match (c)
j=4 i=7 match (b)
j=5 i=8 match (d)

发现错误的模式：

bbcbd!=abcbd

Answer 1

您没有正确计算 KMP 失败数组（或前缀函数）。模式的任何前缀均不以与该前缀的任何后缀相同的字符开头；失败数组应该是

[0, 0, 0, 0, 0]

。