字符串匹配(查找)算法是一类重要的字符串算法(String Algorithm)。有两个字符串, 长度为m的haystack(查找串)和长度为n的needle(模式串), 它们构造自同一个有限的字母表(Alphabet)。如果在haystack中存在一个与needle相等的子串,返回子串的起始下标,否则返回-1。C/C++、PHP中的strstr函数实现的就是这一功能。LeetCode上也有类似的题目,比如#28、#187.
关于KMP,网上有很多很好的资料了,但我看了好久才看基本明白这到底是个什么玩意。于是决定自己总结一下,在这里做个笔记。
Knuth-Morris-Pratt算法,简称KMP,是一个经典的字符串查找算法。Knuth就是传说中的Donald Knuth,著有[The Art of Computer Programming](The Art of Computer Programming)。
我们知道,在进行字符串查找时,应当尽量避免不必要的匹配,以此来提高查找效率。因此Boyer-Moore、Sunday、KMP等算法,都试着在发生失配时,利用模式串或查找串的某种信息来跳过一些无意义的匹配尝试。KMP关注的是模式串的部分匹配信息,这种信息是独立于查找串之外的。
先来看个栗子,图中上面的串是haystack,下面的则是needle。
在上图中的查找过程中,当haystack[5]=c,needle[5]=d时发生失配了。接下来当然要把needle往右移动啦,最Naive办法是只移动一位,而这必然是低效的,图样图森破。
我们先来观察一下这个needle串:
在发生失配的字母d的左边,右一个子串
needle[3...4]=ab
,在needle的最开始,也有一个子串needle[0...1]=ab
。我们直到d才发现失配,说明d之前的串都是能够匹配的,所以haystack串中也有两个ab
。当我们右移needle时,还是要求在至少haystack的后续串中能找到一个ab#ab#
,而如果这俩#恰好分别是c和d,就查找成功了。我想说的就是,这里d失配了,但是d之前的部分匹配串应该被利用起来。如果我们右移needle,使得左边那个ab
跟haystack[3...4]=ab
对应,那我们就成功越过了很多个位置,而且不会有遗漏某个成功匹配的危险。于是我们到了这个状态:
接着发现在haystack[7]=d的时候右失配了:
接着观察needle,发现在needle[4]之前有一个
needle[3]=a
,在needle的开始处needle[0]
也是a
。于是我们右移needle,把needle[0]=a和haystack[6]=a对其:
继续这个过程,直到haystack结束,或者找到一个完整的needle。
在上述过程中,对haystack的搜索是持续向右的,下标没有任何回退。并且对于needle,我们利用部分匹配的串,将其游标往回倒了倒。注意,只是把下标往回倒,重新对齐。(注意这些左移右移什么鬼的,是相对的)
KMP算法正是利用这种部分匹配串的信息,来跳过不必要的匹配尝试。KMP算法定义了一个数组,通常称为next数组。next[i]是一个非负整数,表示的意思是,如果在needle的位置i上发生失配,应该使needle的下标回到哪个位置。例如对于上面的needle串,当needle[5]=d发生失配,我们右移needle使得needle[0..1]和haystack[3...4]对齐。于是在下一轮查找中,我们可以直接从needle[2]=c开始匹配,也就是说,needle的下标由5回退到了2。所以对于此needle,其next[5]=2。
对于KMP算法的理解,难点就在于next数组的计算。这里尝试用自认为比较好理解的表述方式来写一写。
如前所述,next[i]表示当在needle[i]的位置发生失配时,下标i应该倒回的位置,同时也表示,在i的前一个位置,有多长的一个子串是与needle开头部分一样长的。next数组的长度正是needle的长度,并且有,next[0]=0,next[1]=0 (如果有next[1]的话)。next数组的计算是从左往右的,假设我们现在已经完成了next[i]的计算,得到了next=[k],形成了下图这种状况。
图中,整个长条表示的是needle串。已经计算完了next[i]的意思就是说,我们已经知道了如果在i位置失配,应该把下标i重置为几;也就是说,已经知道了在i之前一小串,有一串跟needle的开头部分是一样的,就是图中的两块绿色,它们的长度正是k=next[i]。这两块绿色,前一块是needle[0...k-1]这个子串,后一块是needle[i-k...i-1]的子串。注意,我们在计算next[i]的时候,利用的是needle[i-1]这个字符,而并未访问needle[i]。
接下来将要计算的是next[i+1],我们需要考虑的正是字符needle[i]。我们试着扩展上一次得到的部分匹配串,考虑needle[i]和needle[k],如下图所示,考虑两个蓝色块:
如果needle[i]==needle[k],则上一次得到的部分匹配串可以扩展一个位置,得到这样的情形:
于是我们知道,next[i+1]=k+1,这是比较好理解的。那么如果needle[i]不等于needle[k],咋整?
Calm the hell down, and carry on...
既然next是从左往右计算的,那么needle从0到k这些位置,也是经过同样的计算方式得到的,我们来仔细看下这一段:
next[k]的值是已经知道的,它表示如果在位置k失配,应该回到哪,同时也表示,在k之前有一个长度为next[k]的子串与needle开头部分的一个长度为next[k]的子串是一样长的。现在needle[i]!=needle[k],我们只能寻求更短的部分匹配串了。现在可以确定的是,图中四个绿色的块是相等的串。那如果不能从上面的长绿色块扩展,能不能退而求其次,将本图中的短绿色块扩展呢?所以现在令k=next[k],然后查看新的needle[k]这个字符,如果它等于needle[i],说明这个扩展是可行的,因此next[i+1]=k+1。如果仍然没法匹配,则重复上述过程,继续令k=next[k]...直到找到这样的匹配,或者直到k为0依然没法找到这样的匹配。
接下来用Python实现一下这个求next数组的过程:
def getNxt(s):
nxt=[0]*(len(s))
for i in range(1, len(s)-1):
k=nxt[i]
while k and s[k]!=s[i]:
k=nxt[k]
nxt[i+1]=k+1 if s[k]==s[i] else 0
return nxt
注意如果我们没法扩展部分匹配串,则置next[i+1]为0。也就是说,搜索过程中如果在needle[i+1]失配,则从needle开端位置重新开始匹配。
一旦得到了next数组,字符串的搜索过程就变得很简单了。这个过程的思想是类似于next的求解过程的,本文前面也描述过。直接上代码吧。
def strStr(self, haystack, needle):
if not needle:
return 0
nxt=getNxt(needle)
j=0
for i in range(len(haystack)):
while j and needle[j]!=haystack[i]:
j=nxt[j]
if needle[j]==haystack[i]:
j+=1
if j==len(needle):
return i-j+1
return -1
这里的j是needle的下标,当得到一个匹配时,它加一,如果能加到len(needle),则查找成功了,返回当时的haystack起始下标。如果当前的hays[i]不能与needle[j]匹配,也就是在needle[j]发生了失配,则把j置为next[j],直到找到匹配,或者回到needle开始位置。
简单分析一下算法的复杂度。KMP是一个线性时间复杂度的算法。对于查找函数strStr,主体部分有两层循环,咋会是线性的呢?首先,haystack的下标i是在每次for循环之后都增加1的;其次,while循环对needle做回退,如果站在haystack的视角来看,顶多能回退到已经匹配了的子串那么长,也就是说对haystack的访问顶多就一来一回两次,所以均摊下来是2*len(haystack)的。
也可以把strStr的主体部分改写一下,就更清楚了:
上图中,while循环的跳出条件是m+j>=len(haystack),这里的m是haystack的当前子串的起点,也就说,每次考察的是needle[j]是否匹配haystack[m+j]。如果前一个分支被执行,则i会加1,以至于m+i会加1;如果后一个分支被执行,则要么m加1,要么m+i-next[i],而i>next[i],因此m总会增加。因此不管哪个分支被执行,m+i总会变大,因此时间复杂度是O(n)。
本文遵守知识共享协议:署名-非商业性使用-相同方式共享 (BY-NC-SA)及简书协议转载请注明:作者曾会玩
Reference
[1] Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323–350.
[2] Knuth–Morris–Pratt algorithm, Wikipedia
[3] 插图的一部分灵感激发自某次无意中翻到的博客,找不到链接了,请认领。