Knuth-Morris-Pratt算法

August 8, 2018 · View on GitHub

克努斯-莫里斯-普拉特算法

Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串 S内查找一个词W的出现位置。此算法通过运用对 这个W词在不匹配时,本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

复杂性

  • 时间: O(|W| + |T|) (比较琐碎的O(|W| * |T|)快得多)
  • 空间: O(|W|)

参考