Lesson-44.md

March 26, 2014 · View on GitHub

Lesson 44 - KMP 算法实现

课程任务

参考 Knuth-Morris-Pratt 字符串查找算法，实现字符串查找的 KMP 算法。

重要结论：

  • 当比较过程中发生不匹配时，不需要把搜索位置移回到已经比较过的位置，可以根据前面比较过字符中所包含的部分匹配信息(partial match)，向后移动较多位置，从而提高比较效率。
  • 部分匹配表的作用就是计算向后移动的位数=已匹配的字符数-对应的部分匹配值
  • 最后一个元素的部分匹配值为0，表示找到一个完全匹配，跳过整个匹配字符串继续向后搜索。
  • 部分匹配的本质就是字符串的头部和尾部会有重复，重复部分的长度等于最长的前缀后缀共有元素长度，每次不匹配时需要向后移动的长度就是要确保这个匹配（即前缀和后缀的最多共有元素产生相同比较）能够发生。

参考资料