Algorithm

KMP 算法 思想 KMP 算法, 全程 Knuth-Morris-Pratt 算法, 是一种高效的字符串匹配算法. 它的核心思想是: 在匹配过程中, 当发生文本串(text)与模式串(pattern)不匹配时, 能够利用已匹配过的部分信息, 智能地移动模式串, 从而避免从头开始匹配, 达到提高匹配效率的目的. KMP算法的巧妙之处在于: 它认为, 当发生不匹配时, 将模式串仅仅右移一位是"愚蠢"的. 当某个地方不匹配时, 表明前面实际上有部分内容已经匹配了. 如果直接从头开始匹配, 就浪费了这些信息. 有时前面已经匹配部分会有"重复"的性质, 可以利用这种性质, 让子串一次多移动几步, 从而加速匹配速度. 举例 主串S和模式串P S = BBC ABCDAB ABCDABCDABDE P = ABCDABD 当匹配到下面这种情况时: S = BBC ABCDAB ABCDABCDABDE P = ABCDABD 这里的 D 和上面空格不匹配, 此时保理匹配就直接向右移动一位, 但是通过观察已经匹配的部分 “ABCDAB” 可以发现, 该部分有相同的前后缀 “AB”, 因此可以直接将子串的 “A” 对准主串中后缀 “AB” 里面的 “A”: S = BBC ABCDAB ABCDABCDABDE P = ABCDABD 此时, S 的指针不用改变, 将 P 的指针回到 “C” 的位置就行了. 通过这种方法, 大大提升了效率. ...