KMP算法
KMP 是一种字符串的模式匹配算法,可以在最多只遍历一遍主串的情况下,实现两个字符串的匹配。时间复杂度 O(m+n)
字符串匹配问题
子串的定位操作通常称为串的模式匹配,他求的是字串(通常成为模式串)在主串中的位置。
很容易想到一种朴素的暴力解法。
直接上代码
1 | int Index(string S,string T) |
在上述算法中,分别用计数指针 i,j 指示主串 S 和模式串 T 中当前正在比较字符的位置。从主串 S 的第一个字符开始,与模式串的第一个字符进行比较,若相等,则继续逐个比较后序的字符,否则从主串的下一个字符起,重新和模式串的字符进行比较,以此类推,直到模式串 T 中的每个字符依次和主串中的一个连续的字符序列相等,则匹配成功。否则匹配不成功。
这种暴力尝试的最坏时间复杂度是 O(n*m)其中 n 和 m 是主串和模式串的长度。
演示动画如下
KMP 算法
在上述动画演示中,第三趟匹配中 i=6,j=4 的字符比较不想等,于是又从 i=3,j=0 重新开始比较,然而仔细观察一下就会发现,i=3,j=0、i=4,j=0、i=5,j=0 这三次比较都是不必进行的,因为在第三趟的部分匹配结果上我们就已经知道了主串的第 3、4、5 的字符是 b、c、a。而模式串的第一个字符是 a 我们也是知道的,所以 3、4 两个位置可以直接跳过,因为一定不符合,而 5 的位置不需要比较,因为一定符合,所以可以直接进心 i=6、j=1 的比较。
我们利用一下这个思想改良一下上述算法。动画演示如下
用代码实现一下
1 | int Index(string S,string T,int next[]) |
这段代码和上面的代码的主要有两处改动,第一处是 13 行,匹配失败的时候不回溯而是查表,j 跳转到下一个应该匹配的位置。第二处是第 6 行的判断加上了j == -1
的判断,这相当于一个 flag,代表第一个就匹配失败的意思,下面求 next 数组的过程会提到。
next 数组计算
在上述算法实现中直接使用了一个 next 数组来表示匹配失败之后 j 应该从哪个位置重新匹配。那么这个 next 数组如何计算呢。
以上述模式串 Tabcac
为例:
next[0]一定是-1,这个-1 只是一个 flag 位,只要去不到真正数组中的位置即可,这个标记位代表的意思是第一个就匹配失败,主串指针需要右移。
next[1]一定是 0,模式串的第 1 个匹配失败,主串需要和模式串的第 0 个进行重新匹配。
next[2] = next[3] = 0 没有可以省略的匹配
next[4] = 1,因为如果在 j = 4 的位置匹配失败,那么 j = 3 时匹配成功的,那么 i -1 的位置一定是 a 所以可以省略掉第 0 个位置的判断。
编号 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
T | a | b | c | a | c |
next | -1 | 0 | 0 | 0 | 1 |
代码实现
1 | void get_next(string T,int next[]) |
KMP 算法进一步优化
假如模式串 T = “aaaab”那么 next 数组如下
编号 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
T | a | a | a | a | b |
next | -1 | 0 | 1 | 2 | 3 |
假如在 j = 3 的时候匹配失败,j = 2 而此时 T[2] = T[3] 所以在 2 这里肯定也会失败。j 跳转到 i,而此时 T[1] = T[2]所以 1 这里也会失败。这些比较都是没有意义的,因此可以对 next 数组进行进一步的优化成如下
编号 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
T | a | a | a | a | b |
next | -1 | -1 | -1 | -1 | 3 |
代码实现如下
1 | void get_next(string T,int next[]) |