β

KMP算法

JeyZhang 189 阅读
前言 leetcode上有一道字符串匹配的问题(strStr),直观的做法是遍历原始字符串的每一个子串开始的位置,与匹配串进行比较,如果匹配输出下标;否则返回-1.代码如下: [crayon-555b055f96d62760952128/] 暴力遍历法的时间复杂度为O(m*n),显然每一次匹配失效后从头开始匹配并不高效,如果能够有效的利用匹配字符串的信息,当匹配失败时可以尽量不进行冗余的匹配,于是就有了KMP算法,该算法的时间复杂度为O(n+m). 基本概念 1. 字符串前缀与后缀 首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。例如, “abab”的前缀有”a”,”ab”,”aba”; “abab”的后缀有”bab”,”ab”,”b”; 2. 最大前后缀匹配长度 最大前后缀匹配长度是指以当前字符结尾的字符串中所有的前缀和后缀,相匹配的最大长度;举一个例子,对于字符串”abab”而言,对于每一个字符所计算出的最大前后缀匹配长度分别为0,0,1,2.后续的next数组中的元素即为以当前字符结尾的字符串的最大前后缀匹配长度。 next数组为每一次匹配失败时,指示了最大能够移动的位数,从而提高了匹配的效率。举个例子,假设原字符串S为”ababcababd”,匹配串T为”ababd”,第一次匹配时,字符串S和T的前4个字符均能匹配,第5个字符匹配失败,此时如果按照暴力匹配则继续从S的第2个字符,T的第0个字符重新开始匹配;但是通过观察我们发现,匹配字符串S的第5个字符’c’时并不需要重新从T的第0位开始,只需要从T的第3位开始,因为S中第5位字符’c’的前两个字符”ab”之前已经能够和T的后缀”ab”匹配了,而”ab”也是字符串T的前缀,我们知道如果从头开始匹配,这两个字符肯定是可以匹配成功的(这就是为什么需要记录next数组),所以只需要匹配T中对应的后一位字符即可。 3. next数组 之前说了next数组中存放的是以当前字符为结尾的最大前缀和后缀的公共长度,指示了当字符串匹配失败时,模式串T重新比较的位置。求解next数组本身就非常巧妙,可以用最原始的方法,即列出所有的前缀和后缀进行匹配找出公共的最大长度。下面有一种巧妙的方法: [crayon-555b055f96d6f164693539/] 4. 如何利用next数组进行字符串匹配 设立两个指针i和j,分别指向字符串S和T,如果指向的字符匹配则同时移动i和j指针;如果匹配失败,则移动i指针,但是j指针不需要从头匹配了,只需要跳转到next[j]的位置(正如2中所说的那样)。 [crayon-555b055f96d77603677696/]   小结 KMP算法虽然时间复杂度较低,但是实际使用较少。用得比较多的字符串匹配算法还有BM算法和Sunday算法,后续继续更新。  
作者:JeyZhang
To be Smarter & Stronger
原文地址:KMP算法, 感谢原作者分享。

发表评论