记录生活中的点点滴滴

0%

KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

暴力匹配算法

如果用暴力匹配的思路,并假设现在 str1 匹配到 i 位置,子串 str2 匹配到 j 位置,则有:

  1. 如果当前字符匹配成功(即 str1[i] == str2[j]),则 i++,j++,继续匹配下一个字符
  2. 如果失配(即 str1[i]! = str2[j]),令 i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为 0。
  3. 用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量 的时间。(不可行!)

暴力匹配算法实现代码:

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
//字符串暴力匹配
public class ViolentMatch {
public static void main(String[] args) {
String str1 = "干卡视角经济o兄弟是及科目你好网不好hello兄弟是的OK";
String str2 = "o兄弟是的";//在22
int index = match(str1,str2);
System.out.println(index);
}

//暴力匹配
private static int match(String str1, String str2) {
char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
int c1Len = c1.length;
int c2Len = c2.length;
int i = 0;
int j = 0;
while (i < c1Len && j < c2Len){
if(c1[i] == c2[j]){
i++;
j++;
}else {
i = i - (j-1);
j = 0;
}
}
if(j == c2Len){
return i-j;
}
return -1;
}
}

KMP算法

先说几点重要信息:

KMP算法充分利用了目标字符串ptr的性质(比如里面部分字符串的重复性,即使不存在重复字段,在比较时,实现最大的移动量)。

KMP算法利用已经部分匹配这个有效信息,保持 i 指针不回溯,通过修改 j 指针,让模式串尽量地移动到有效的位置

整个KMP算法的重点就在于当某一个字符与主串不匹配时,我们应该知道 j 指针要移动到哪?

小试牛刀

接下来我们自己来发现 j 的移动规律:

如果 C 和 D 不匹配了,我们要把j移动到哪?显然是第1位 B。为什么?因为前面有一个 A 相同啊。如下所示:

我们再看下面的情况:

此时 C 和 B 不匹配了,那么指针 j 应该移到第2位 C 上,因为前面两个字母 A B是相同的,如下:

OK,到这里我们就能看到一些端倪,当匹配失败时,j要移动的下一个位置k。存在着这样的性质:最前面的 k个字符和j之前的最后k个字符是一样的

来点概念

下面给出一些概念,我们就会更透彻了。

字符串的前缀、后缀、部分匹配值

前缀:指除最后一个字符外,字符串的所有头部子串

后缀:指除第一个字符外,字符串的所有尾部子串

部分匹配值:字符串前缀和后缀的最长相等前后缀长度

不理解,没关系啊,且看一个例子就全都透彻了,以 ababa 为例:

  • a 的前缀和后缀都是空,部分匹配值为0
  • ab 的前缀为 a ,后缀为 b,部分匹配值为0
  • aba 的前缀为 a ab ,后缀为 a ba ,两者共有部分为 a ,所以部分匹配值为1
  • abab 的前缀为 a ab aba ,后缀为 b ab bab ,部分匹配值为 2
  • ababa 的前缀为 a ab aba abab ,后缀为 a ba aba baba ,部分匹配值为3

趁热打铁

下面我们自己搞一个表格,上面写一个字符串,下面为从头开始到其下标的子串的部分匹配值,我们就以 abaabb 为例:

字符串 a b a a b b
部分匹配值 0 0 1 1 2 0

我们看看如果匹配失败了,按照我们小试牛刀的样子,j 指针该怎么移动,还看上面那张图:

最后一位 B 匹配失败,j 指针移动到了 2 位置,其实就是我们上面 它的前一个部分匹配值,其他的也同理。

我们每次匹配失败就去找它前一个元素的部分匹配值,不方便。我们将那个部分匹配值那一行向右移一位,这样匹配出错直接找它自己的就行,我们把这一行命名为 next 数组,出错 j 指针就去指向它的 next[j]。如下:

字符串 a b a a b b
next数组 -1 0 0 1 1 2

对了,还有第一个下标的问题,第一个就出错了,我们将它的next下标标记为 -1,表示需要移动 i 指针了,而不是 j 指针。

先说清楚:next数组的含义为模式串p[j]之前前缀和后缀相等的个数,若都不相等则为0。(特殊情况,没有前缀和后缀时,则为-1,如next[0]=-1)

如果我们得到了被匹配串的 next 数组,那么接下来去求其在主串中的位置,应该还是很简单的了。

下面我们先不管怎么得到next数组,假设这一步已经搞定了,先写 KMP 算法的主干部分,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//kmp匹配
public static int kmp(String str1, String str2) {
char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
int c1Len = c1.length;
int c2Len = c2.length;
int i = 0;
int j = 0;
int[] next = getNext(str1);
while (i < c1Len && j < c2Len){
if(j==-1 || c1[i] == c2[j]){
i++;
j++;
}else {
j = next[j];
}
}
if(j == c2Len){
return i-j;
}
return -1;
}

相比我们之前写的暴力匹配算法,其实就是前面多以一个获取next数组,后面判断条件和步骤稍微改一下,只要上面理解了之后应该不难看懂的。

迎战BOSS—递推next数组

所以其实关键的就是获取next数组,我们要完成这个函数,传入一个字符串,得到它的next数组。

1
2
3
4
//求next数组
public static int[] getNext(String str){

}

们很容易的可以知道,next[0] = -1,next[1] = 0。那么当 j>1时,如果我们已知了next[j],那么next[j+1]怎么求得呢???

我们分两种情况分析:pk == pj pk != pj

  1. 当 pk == pj,next[j + 1] = next[j] + 1 = k + 1,代表字符E前的模式串中,有长度k+1 的最大公共前后缀。

    模式串 A B C D A B C E
    部分匹配值 0 0 0 0 1 2 3 0
    next -1 0 0 0 0 1 2 ?
    索引 p0 pk-1 pk pk+1 pj-k pj-1 pj pj+1
  2. pk != pj,也就是字符A前的模式串中没有长度为k+1的最大公共前后缀,所以next[j + 1] = next[j] + 1不再适用,我们只能寻找更短的最大公共前后缀。

    模式串 A B D A B C A B D A B D A
    next -1 0 0 0 1 2 0 1 2 3 4 5
    索引 p0 p1 p2 p3 pk-1 pk pk+1 pk+2 . . pj-1 pj pj+1

    这样看来,如果我们能在p0p1…pk中不断递归索引 k = next[k]

    • 如果找到一个字符pk’,就是 pj D的话,那么最大公共前后缀长度就为k’+1,即 next[j+1] = k’+1
    • 如果找不到,最后k’等于-1,next[j+1] 仍然= k’+1

为什么递归前缀索引 k = next[k],就能找到长度更短的相同前缀后缀呢???我们用这张图来分析:

在pk != pj时,k = next[k],用pnext[k]去跟pj继续匹配。为什么不用其他值和pj匹配呢?我们可以看到,在pj之前,有一段长度为k的已匹配串;在pk之前有一段蓝色的已匹配串,说明pk字符前有一段长度为next[k]的最大公共前后缀(蓝色的那段)。如果pk != pj,说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj,那么我们只能找更短的最大公共前后缀,此时因为pk和pnext[k]前面的蓝色串已完全匹配,如果pnext[k]能和pj匹配 ,那么我们便找到了我们需要的串。如果还是不匹配,下一步pnext[next[k]…]去跟pj继续匹配,直到找到长度更短公共前后缀。

得了,差不多了,下面给出求next数组的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//求next数组
public static int[] getNext(String str){
char[] p = str.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length-1){
if(k == -1 || p[j]==p[k]){
next[++j] = ++k;
}
else
k = next[k];
}
return next;
}

最后一击

其实还有一个问题,我们看一下下面的情况:

显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]

所以下一步我们应该是把j移动到第1个元素咯:

不难发现,这一步是完全没有意义的。因为后面的B已经不匹配了,那前面的B也一定是不匹配的,同样的情况其实还发生在第2个元素A上。

显然,发生问题的原因在于P[j] == P[next[j]]

所以我们也只需要添加一个判断条件即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//求nextval数组
public static int[] getNextval(String str){
char[] p = str.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length-1){
if(k == -1 || p[j]==p[k]){
if(p[++j]==p[++k])// 当两个字符相等时要跳过
next[j] = next[k];
else
next[j] = k;
}
else
k = next[k];
}
return next;
}

这个其实就是我们的 nextval 数组。

我们看看字符串 abaacdaaaab 的 next数组 和 nextval 数组:

0 1 2 3 4 5 6 7 8 9 10
字符串 a b a a c d a a a a b
next -1 0 0 1 1 0 0 1 1 1 1
nextval -1 0 -1 1 1 0 -1 1 1 1 0

nextval 数组的求法我们遵循一个原则,那就是同变 不同不变。其中第一个元素的nextval值和他的next值一样为-1,第二个元素是b,他的next值为0,0对应的元素为a,不同,即不变,nextval为0,同理第三个元素为a,a的next为0,0下面的就是a,相同,即变!将第三个元素的nextval值和刚刚比较的那个元素的nextval值保持一致,以此类推。

完整代码

终于结束了,我已经虚脱了,不写了不写了,最后把所有完整的代码贴上来,溜了溜了。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class KMP {
public static void main(String[] args) {
String str1 = "bacbababadababacambabacaddababacasdsd";
String str2 = "ababaca";//在10
int index = kmp(str1,str2);
System.out.println(index);
}
//求next数组
public static int[] getNext(String str){
char[] p = str.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length-1){
if(k == -1 || p[j]==p[k]){
next[++j] = ++k;
}
else
k = next[k];
}
return next;
}
//求nextval数组
public static int[] getNextval(String str){
char[] p = str.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length-1){
if(k == -1 || p[j]==p[k]){
// next[++j] = ++k;
if(p[++j]==p[++k])// 当两个字符相等时要跳过
next[j] = next[k];
else
next[j] = k;
}
else
k = next[k];
}
return next;
}
//kmp匹配
public static int kmp(String str1, String str2) {
char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
int c1Len = c1.length;
int c2Len = c2.length;
int i = 0;
int j = 0;
int[] next = getNextval(str1);
while (i < c1Len && j < c2Len){
if(j==-1 || c1[i] == c2[j]){
i++;
j++;
}else {
j = next[j];
}
}
if(j == c2Len){
return i-j;
}
return -1;
}
}