双向迭代器是否有任何Knuth-Morris-Pratt算法实现?在Boost.Algorithm中,有随机访问迭代器的版本。
让我们来看看一个标准实现。我们实际需要随机访问的唯一地方是在跳转i = p[i]
后比较pattern[i]
和当前角色。而不是直接访问pattern[i]
(在双向迭代器的最坏情况下,这需要线性时间),我们可以在构建过渡表时将下一个字符c
与p[i]
一起存储在模式中。
但是,它并没有那么有用。为每个i
存储一个符号本质上与将模式复制到支持随机访问的结构中是一回事,因此直接执行此操作会更容易。