KMP算法解决字符串匹配问题

要解决的问题

假设字符串str长度为N,字符串match长度为M,M <= N, 想确定str中是否有某个子串是等于match的。返回和match匹配的字符串的首字母在str的位置,如果不匹配,则返回-1

OJ可参考:LeetCode 28. 实现 strStr()

暴力方法

从str串中每个位置开始匹配match串,时间复杂度O(M*N)

KMP算法

KMP算法可以用O(N)时间复杂度解决上述问题。

流程

我们规定数组中每个位置的一个指标,这个指标定义为

这个位置之前的字符前缀和后缀的匹配长度,不要取得整体。

例如: ababk 这个字符串,k位置的指标为2, 因为k之前位置的字符串为abab

前缀ab 等于 后缀ab,长度为2,下标为3的b的指标为1,因为b之前的字符串aba ,前缀a 等于后缀a, 长度为1。

人为规定:**0位置的指标是-1,1位置的指标0**

假设match串中每个位置我们都已经求得了这个指标值,放在了一个next数组中,这个数组有助于我们加速整个匹配过程。

我们假设在某个时刻,匹配的到的字符如下

image

其中str的i..j一直可以匹配上match串的0...m, str中的x位置和match串中的y位置第一次匹配不上。如果使用暴力方法,此时我们需要从str的i+1位置重新开始匹配match串的k位置,而KMP算法,利用next数组,可以加速这一匹配过程,具体流程是,依据上例,我们可以得到y位置的next数组信息,假设ynext数组信息是2,如下图

image

如果ynext数组信息是2,那么0...k 这一段完全等于f...m这一段,那么对于match来说,当y位置匹配不上x位置以后, 可以直接让x位置匹配ynext数组位置p上的值,如下图

image

如果匹配上了,则x来到下一个位置,p来到下一个位置继续匹配,如果再次匹配不上,假设p位置的next数组值为0, 则继续用x匹配pnext数组位置0位置上的值,如下图

image

如果x位置的值依旧不等于0位置的值,则宣告本次匹配失败,str串来到x下一个位置,match串从0位置开始继续匹配。

next数组求解

next数组的求解是KMP算法中最关键的一步,要快速求解next数组,需要做到当我们求i位置的next信息时,能通过i-1next数组信息加速求得,如下图

image

当我们求i位置的next信息时,假设j位置的next信息为6,则表示

image

m...n这一段字符串等于s...t这一段字符,此时可以得出一个结论,如果:

x位置上的字符等于j位置上的字符,那么i位置上的next信息为j位置上的next信息加1,即为7。如果不等,则继续看x位置上的next信息,假设为2,则有:

image

此时,判断q位置的值是否等于j位置的值,如果相等,那么i位置上的next信息为x位置上的next信息加1,即为3,如果不等,则继续看q位置上的next信息,假设为1,那么有

image

此时,判断p位置的值是否等于j位置的值,如果相等,那么i位置上的next信息为q位置上的next信息加1,即为2,如果不等,则继续如上逻辑,如果都没有匹配上j位置的值,则i位置的next信息为0。

主流程代码复杂度估计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class LeetCode_0028_ImplementStrStr {
public static int strStr(String str, String match) {
if (str == null || match == null || match.length() > str.length()) {
return -1;
}
if (match.length() < 1) {
return 0;
}
char[] s = str.toCharArray();
char[] m = match.toCharArray();
int l = m.length;
int[] next = getNextArr(m, l);
int x = 0;
int y = 0;
while (y < s.length && x < l) {
if (s[y] == m[x]) {
y++;
x++;
} else if (x != 0) {
x = next[x];
} else {
y++;
}
}
return x == l ? y - x : -1;
}

// 求解next数组逻辑
private static int[] getNextArr(char[] str, int l) {
if (l == 1) {
return new int[]{-1};
}
int[] next = new int[l];
next[0] = -1;
next[1] = 0;
int i = 2; // 目前在哪个位置上求next数组值
int cn = 0; // 前后缀最长字符的长度,也表示下一个要比的信息位置
while (i < next.length) {
if (str[i - 1] == str[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
}

next数组的求解流程时间复杂度显然为O(N),现在估计主流程的复杂度,主流程中,x能取得的最大值为str字符串的长度N,定义一个变量x-y,能取得的最大值不可能超过N(即当x = N,y=0时候),在主流程的wile循环中,有三个分支

1
2
3
4
5
6
7
8
9
10
while (y < s.length && x < l) {
if (s[y] == m[x]) {
y++;
x++;
} else if (x != 0) {
x = next[x];
} else {
y++;
}
}

我们考虑这三个分支对于yy - x变化范围的影响

分支 y y - x
x++; y++ 推高 不变
x = next[x] 不变 推高
y++ 推高 推高

如上分析,yy-x都不可能降低,且三个分支只能中一个,所以,而yy-x的最大值均为N,所有分支执行总推高的次数不可能超过2N。即得出主流程的复杂度O(N)

KMP算法应用

求一个字符串的旋转词(详见:LeetCode 796)

思路

将这个字符串拼接一下, 比如原始串为:123456,拼接成:123456123456

如果匹配的字符串是这个拼接的字符串的子串,则互为旋转词。

一棵二叉树是否为另外一棵二叉树的子树(详见:LeetCode 572)

思路

先将两棵树分别序列化为数组A和数组B,如果B是A的子串,那么A对应的二叉树中一定有某个子树的结构和B对应的二叉树完全一样。

更多

算法和数据结构笔记

参考资料