什么是KMP
三位学者发明的:Knuth,Morris和Pratt算法
KMP有什么用
KMP主要应用在字符串匹配上。
KMP的主要思想是「当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头开始再去做匹配了。」
那么如何记录已经匹配的文本内容,是KMP的重点,也是next数组肩负的重任。
前缀表
next数组就是一个前缀表(prefix table)。
前缀表有什么作用呢?
「前缀表是用来回溯的,意味着在某个字符失配时,前缀表会告诉你下一步匹配中,模式串应该跳到哪个位置。
所以前缀表记录的是模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配的位置。」
为了清楚的了解前缀表的来历,我们来举一个例子:
要在文本串:aabaabaafa中查找是否出现过一个模式串:aabaaf。
可以看出,文本串中第六个字符b 和 模式串的第六个字符f,不匹配了。那如果暴力匹配发现不匹配,就要从头匹配了。
但如果使用前缀表,就不会从头匹配,而是从上次已经匹配上的内容开始匹配,找到了模式串中第三个字符b继续开始匹配。
所以什么是前缀表:「下表i之前(包括i)的字符串中,有多大长度的相同前缀后缀。」
验证前缀表的功能是否真如上面所说的那般强大
刚刚匹配的过程在下表5的地方遇到不匹配,模式串是指向f,如图
然后就找到了下表2,指向b,继续匹配:如图:
那么我们通过观察发现「下表5之前这部分的字符串(也就是字符串aabaa)的最长相等的前缀 和 后缀字符串是 子字符串aa ,因为找到了最长相等的前缀和后缀,匹配失败的位置是后缀子串的后面,那么我们找到与其相同的前缀的后面重新匹配就可以了。」
所以前缀表具有告诉我们当前位置匹配失败,跳到之前已经匹配过的地方的能力。
如何计算前缀表
长度为前1个字符的子串a,最长相同前后缀的长度为0。
长度为前2个字符的子串aa,最长相同前后缀的长度为1
长度为前3个字符的子串aab,最长相同前后缀的长度为0
以此类推:
长度为前4个字符的子串aaba,最长相同前后缀的长度为1。
长度为前5个字符的子串aabaa,最长相同前后缀的长度为2。
长度为前6个字符的子串aabaaf,最长相同前后缀的长度为0。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素,如图:
可以看出「前缀表里的数值代表着就是:当前位置之前的子串有多大长度相同的前缀后缀。」重要重要重要
找到的不匹配的位置, 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要看前一个字符的前缀表的数值呢,因为要找前面字符串的最长相同的前缀和后缀。
前一个字符的前缀表的数值是2, 所以把下表移动到下表2的位置继续匹配。
最后就在文本串中找到了和模式串匹配的子串了。
前缀表有什么问题
看这个位置红框的位置,如果要找下表1 所对应 前缀表里的数值的时候,前缀表里的数值依然是1,然后就要跳到下表1的位置,如此就「形成了一个死循环」。
「如何怎么避免呢,就把前缀表里的数值统一减一, 开始位置设置为-1 。」 这一点对理解后面KMP代码很重要!!
这样就避免的死循环,只不过后续取 前缀表里的数值的时候,要记得再+1,才是我们想要的值。
「最后得到的新前缀表在KMP算法里通常用一个next数组来表示。」
注意这个next数组就根据模式串求取的。
使用next数组来匹配
有了next数组,就可以根据next数组来 匹配文本串s,和模式串t了。
注意next数组是新前缀表(旧前缀表统一减一了)。
时间复杂度分析
再来看一下时间复杂度, 假设文本串长度为n,模式串长度为m
其中n为文本串长度,m为模式串长度,因为在匹配的过程中,根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n),但之前还要单独生成next数组,时间复杂度是O(m)所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n * m),所以「KMP在字符串匹配中极大的提高的搜索的效率。」