KMP 和 Rabin-Karp Sliding window 算法是否用于模式匹配？
Are KMP and Rabin-Karp Sliding window algorithms for pattern match?
我正在尝试了解模式匹配的 Sliding Window 算法。我遇到了 KMP 和 Rabin-Karp，这些看起来是使用 Sliding Window 方式在文本中查找模式。我们可以将 KMP 和 Rabin-Karp 类型的 Sliding window algorithm 分类吗？
分类总是很棘手。如果没有对我们所谈论的内容进行严格定义，我们就无法真正做到这一点，而这样的定义通常是相当随意的。
也就是说，在我的脑海中，滑动 window 算法有一个 fixed-sized window 它沿着序列移动，在每次迭代中移动window 移出并从右侧移入相同的量。根据该定义，Rabin-Karp 显然是一种滑动 window 算法。在每次迭代中，它从左边删除一个字符并从右边添加一个字符以更新哈希值。
Knuth-Morris-Pratt 不会这样做。你当然可以认为它有一个 window，但这个 window 是你当前匹配的模式前缀的边界，当你可以扩展匹配时 window 大小增长，而当你无法匹配时，它会缩小到较短边框的长度。在算法的 运行 期间，大小从零到模式的长度不等。
也就是说，我对滑动 window 算法的定义是任意的，其他人肯定会不同意。
这个定义有用吗？我觉得是这样的。滑动 window 的想法是一种抽象，可以让我们构建新的算法。允许可变大小 windows 是否会丢失任何东西？也许不是。但是 KMP 和 RK 有什么共同点，我们可以抽象出一些可能有用的东西？
我不认为有很多。他们从左到右扫描字符串（不像 Boyer-Moore），但除此之外他们没有太多共享。一种是基于散列的，另一种是基于边界的。细节完全不同
你总是可以想出一个 class 两者都适合的化身，但除非 class 告诉你一些超出琐碎的事情，否则它没有多大用处，会是我的意见。
我正在尝试了解模式匹配的 Sliding Window 算法。我遇到了 KMP 和 Rabin-Karp，这些看起来是使用 Sliding Window 方式在文本中查找模式。我们可以将 KMP 和 Rabin-Karp 类型的 Sliding window algorithm 分类吗？
分类总是很棘手。如果没有对我们所谈论的内容进行严格定义，我们就无法真正做到这一点，而这样的定义通常是相当随意的。
也就是说，在我的脑海中，滑动 window 算法有一个 fixed-sized window 它沿着序列移动，在每次迭代中移动window 移出并从右侧移入相同的量。根据该定义，Rabin-Karp 显然是一种滑动 window 算法。在每次迭代中，它从左边删除一个字符并从右边添加一个字符以更新哈希值。
Knuth-Morris-Pratt 不会这样做。你当然可以认为它有一个 window，但这个 window 是你当前匹配的模式前缀的边界，当你可以扩展匹配时 window 大小增长，而当你无法匹配时，它会缩小到较短边框的长度。在算法的 运行 期间，大小从零到模式的长度不等。
也就是说，我对滑动 window 算法的定义是任意的，其他人肯定会不同意。
这个定义有用吗？我觉得是这样的。滑动 window 的想法是一种抽象，可以让我们构建新的算法。允许可变大小 windows 是否会丢失任何东西？也许不是。但是 KMP 和 RK 有什么共同点，我们可以抽象出一些可能有用的东西？
我不认为有很多。他们从左到右扫描字符串（不像 Boyer-Moore），但除此之外他们没有太多共享。一种是基于散列的，另一种是基于边界的。细节完全不同
你总是可以想出一个 class 两者都适合的化身，但除非 class 告诉你一些超出琐碎的事情，否则它没有多大用处，会是我的意见。