论坛 › C\C++交流 › KMP算法优化没问题？

麻麦皮 发表于 2020-5-31 21:27:44

KMP算法优化没问题？

KMP优化直接跳过了无意义的情况，例如
S        a a a a b a a a a a
T        a a a a a
next        0 0 0 0 0

直接变成了
S        a a a a b a a a a a
T                      a a a a a
next                      0 0 0 0 0

如果是
S        a a a a b a
T        a a b
next        0 0 2

则

S        a a a a b a        →        S a a a a b a
T              a a b                T         a a b
next           0 0 2                next   0 0 2

完全错过了匹配的答案，KMP算法优化是不是会像上述情况一样错过了答案

永恒的蓝色梦想 发表于 2020-5-31 21:29:27

不会。尽管我不知道为什么。

麻麦皮 发表于 2020-5-31 21:33:20

永恒的蓝色梦想 发表于 2020-5-31 21:29
不会。尽管我不知道为什么。

我列举的下面这种情况错过了啊

永恒的蓝色梦想 发表于 2020-5-31 21:38:31

麻麦皮 发表于 2020-5-31 21:33
我列举的下面这种情况错过了啊

不知道{:10_277:}
相信 KMP 就对了{:10_256:}

查看完整版本: KMP算法优化没问题？