KMP(一) 模式匹配算法推导 --《部分匹配表》
概述:本文主要在理论层面上分析KMP的基本实现原理以及《部分匹配表》推导过程;不涉及代码实现;如果您对KMP的实现代码(OC)实现感兴趣,可参考:
KMP(一) 模式匹配算法推导 --《部分匹配表》
KMP(二) 模式匹配算法实现
KMP(三) 字符串快速匹配示例
一: KMP主要解决的问题:
KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者！！
KMP算法要解决的问题就是在字符串（也叫主串,下文统一称"P"）中快速高效匹配子串(下文统一称"S")并确定S在P中位置的问题。说简单点就是我们平时常说的关键字(词)搜索。
二. 字串朴素匹配算法实现:
看一个朴素匹配算法示例:
主串: P="BBC ABCDAB ABCDABCDABDE" 长度为Length_p
字串: S = "ABCDABD" 长度为Length_s
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
因为B与A不匹配，搜索词再往后移。
就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
接着比较字符串和搜索词的下一个字符，还是相同。
直到字符串有一个字符，与搜索词对应的字符不相同为止。
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍,很明显P的位置在回溯。分析朴素匹配算法时间复杂度为:
O((Length_p - Length_s + 1) * Length_s)
为方便后续说明,我们来约定一组表达规则:
主串 P 和字串 S 中有以下表达,示例如:
P[0] = "B"
P[4] = "A"
P[0~5]="BBC AB"
S[0] = "A"
S[2]="C"
S[1~3]="BCD"
我们观察一下此时字串 S 和 主串P:
以下重要:
当S[0~5] = P[4~9] 并且 S[6] != P[10]时,S[0~3] 内没有重复的字符,而切S[0~3] =P[4~7],所以在进行下一次比较时,我们可以直接将字串S移动至主串P的P[8] 位置开始比较,同时保持P的上一次查找位置不变(P[10]), 而不是像上图一样从P[5]开始循环比较,因为此时的P[5~8] 不可能与S(主要看S[0~3])匹配 ;这样效率会大大提升;接下来看KMP是如何做的;
三. KMP算法示例分析:
KMP核心原则: 保持主串P上次查找位置(index_p)不回溯,移动字串S到合适的位置(index_s),下次比较起始位置分别为P[index_p]和S[index_s],不在比较P[0~index_p] 和 S[0~index_s],从而达到简化匹配的计算过程;具体示例如下:
这里要引入一个《部分匹配表》概念;部分匹配表推导过程稍后做解释;我们要做的先学会如何利用《部分匹配表》去实现KMP模式匹配,从而理解KMP的匹配过程;字串移位计算公式如下:
移动位数(S) = 已匹配的字符数 - 对应的部分匹配值
接着上述利用《部分匹配表》匹配分析:
7.
已知空格与D不匹配时，前面6个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，照上面的公式算出向后移动的位数：
因为 6 - 2 等于4，所以将S向后移动4位。
8.
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应B的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。
9.
因为空格与A不匹配，而S已经到达最左端,故P继续后移一位。
10.
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。
11.
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。
四. 《部分匹配表》计算过程
首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。注意:此处有个组合的概念,表达不同于KMP 算法实现中的前缀和后缀
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
1. "A"的前缀和后缀都为空集，共有元素的长度为0；
2. "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
3. "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
4. "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
5. "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
6. "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
7. "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
