摘要 串是一种数据元素类型只能为字符的线性数据结构,可以理解为字符序列。按存储结构也可以分为顺序串和链式串,一般以顺序串为代表,定义在串上的操作,如求串长,判断空串,判断串是否为满,指定位置插入字符,指定位置删除字符,这些操作与线性表中一模一样,所以,有兴趣的读者可以参照本系列博客数据结构-线性表进行阅读。对于串,主要算法有模式匹配,而本文所讲的重点也是串的KMP模式匹配算法。

串的定义

串是一种类似线性表的线性数据结构,其数据类型只能为字符,下面是顺序串的定义,可以发现与顺序表的定义一模一样。

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
class SeqString{
public static final int STRING_SIZE = 100;
private char data[] = null;
private int length = 0;

public SeqString(){
data = new char[STRING_SIZE];
}

public SeqString(char[] data){
this.data = new char[STRING_SIZE];
for(int i=0;i<data.length;i++){
this.insert(i+1, data[i]);
}
}

public int length(){
return this.length;
}

public boolean isEmpty(){
return this.length == 0;
}

public boolean isFull(){
return this.length == STRING_SIZE;
}

public boolean insert(int pos, char val){
if(pos < 1 || pos > length+1)
return false;
if(this.isFull())
return false;
for(int i=length-1;i>=pos-1;i--)
data[i+1] = data[i];
data[pos-1] = val;
this.length++;
return true;
}

public char delete(int pos){
if(pos < 1 || pos > length)
return '#';
if(this.isEmpty())
return '#';
char c = data[pos-1];
for(int i=pos;i<length;i++)
data[i-1] = data[i];
this.length--;
return c;
}

public String toString(){
return new String(this.data,0,this.length);
}
}

关于串的结构类型定义,这里就不再赘述。下面介绍串的模式匹配算法。先以朴素匹配算法作为引例,然后在此基础之上,介绍KMP算法。

朴素匹配算法

串的朴素匹配算法,实现简单,容易理解,也可以认为是一种暴力匹配算法:

将主串与模式串中的字符进行一个一个的比对:

  • 如果匹配成功,主串与模式串各自递进向前滑动一位;
  • 如果匹配失败,那么一切从头来过,模式串重新从0位置开始,主串从下一个位置开始,这里的下一个位置的计算(i-j+1,因为j走了多少,i也走了多少,然后下一个也就是加1).

循环结束条件为模式串匹配完毕,即在主串中找到了所有模式串的字符,或者主串都走完了,还没有找到与模式串匹配的子串,结束匹配,返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* [indexOf description]
* @param t [mask string]
* @return [first pos of mask in main string]
*/
public int indexOf(SeqString t){
SeqString s = this;
int i=0,j=0;
while(i < s.length && j < t.length){
if(s.data[i] == t.data[j]){
i++;
j++;
}else{
j=0;
i = i-j+1;
}
}
if(j == t.length)
return i-j;
else
return -1;
}

KMP模式匹配算法

上述朴素匹配算法,实现简单,易于理解,但是其时间复杂度时$O(m*n)$,其中m是主串长度,n是模式串长度。

算法的关键在于,当主串中i位置字符与模式串中j位置字符失配时,模式串从0开始,主串也回溯到i-j+1的位置,其实如果充分利用模式串失配位置字符之前的字符序列信息,就可以发现,主串不需要回溯,只需要回溯模式串即可,而且模式串每次回溯的步长可以根据失配位置之前的字符隐含关系来确定,失配位置之前的所有字符如果拥有相同前缀和后缀字符,那么模式串就可以不用回溯到开始位置,而只需要回溯到最长公共前缀的下一个位置即可。这样主串不用回溯,模式串减少回溯的位置,该算法的时间复杂度变为$O(m+n)$。

Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。

next 数组的计算

定义next数组为模式串中每一个字符之前的最长公共前缀后缀的长度,同时定义next[0] = -1。

对于给定的模式串:ABCDABD,它的最大长度表及next 数组分别如下:

next

上图中最大长度值为该字符位置的最长公共前缀与后缀长度,前最大长度值表向右移动一位,并将next[0]赋值为-1就得到了next数组。模式串next数组的求法是KMP算法中最难理解的部分。它需要对模式串进行递推搜索:

  • 如果对于值k,已有p0 p1, …, pk-1 = pj-k pj-k+1, …, pj-1,相当于next[j] = k。
    • next[j] = k 代表p[j] 之前的模式串子串中,有长度为k 的相同前缀和后缀
    • 有了这个next 数组,在KMP匹配中,当模式串中j 处的字符失配时,下一步用next[j]处的字符继续跟文本串匹配,相当于模式串向右移动j - next[j] 位。
  • 递推问题:已知next [0, …, j],如何求出next [j + 1]呢?
    • 若p[k] == p[j],则next[j + 1 ] = next [j] + 1 = k + 1
    • 若p[k ] ≠ p[j],如果此时p[ next[k] ] == p[j ],则next[ j + 1 ] = next[k] + 1,否则继续递归前缀索引k = next[k],而后重复此过程。

为何递归前缀索引k = next[k],就能找到长度更小的相同前缀后缀呢?这又归根到next数组的含义。为了寻找长度相同的前缀后缀,我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配,如果pk 跟pj 失配,下一步就是用p[next[k]] 去跟pj 继续匹配,如果p[ next[k] ]跟pj还是不匹配,则下一步用p[ next[ next[k] ] ]去跟pj匹配。。相当于在不断的递归k = next[k],直到要么找到长度更小的相同前缀后缀,要么没有长度更小的相同前缀后缀。

下面这段代码展示了模式串next数组的求法,其中data[k]表示前缀,data[j]表示后缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public int[] next(){
int next[] = new int[length];
next[0] = -1;

int j = 0, k = -1;
while(j < length-1){
if(k == -1 || data[k] == data[j]){
k++;
j++;
next[j] = k;
}else{
k = next[k];
}
}

return next;
}

KMP算法实现

有了模式串next数组,再来实现KMP算法就变得简单很多了。

KMP算法相对于朴素算法的改进在于,如果模式串在j位置失配,主串无需回溯,模式串每次回溯到next[j]位置。

下面是KMP算法的实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int indexOf_KMP(SeqString t){
SeqString s = this;
int i=0,j=0;
int next[] = t.getNext();

while(i < s.length && j < t.length){
if(j == -1 || s.data[i] == t.data[j]){
i++;
j++;
}else{
j = next[j];
}
}
if(j == t.length)
return i-j;
else
return -1;
}

next 数组的优化

如果用之前的next 数组方法求模式串“abab”的next 数组,可得其next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当它跟下图中的文本串去匹配的时候,发现b跟c失配,于是模式串右移j - next[j] = 3 - 1 =2位。

next优化1

右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知p.data[3] = b,与s.data[3] = c失配,在3位置失配,由于next[3]=1,而右移两位之后,让p.data[1] = b 再跟s.data[3]匹配时,必然失配。问题出在哪呢?

next优化2

问题出在不该出现p.data[j] = p.data[ next[j] ]。为什么呢?理由是:当p.data[j] != s.data[i] 时,下次匹配必然是p.data[ next [j]] 跟s.data[i]匹配,如果p.data[j] = p.data[ next[j] ],必然导致后一步匹配失败(因为p.data[j]已经跟s.data[i]失配,然后你还用跟p.data[j]等同的值p.data[next[j]]去跟s.data[i]匹配,很显然,必然失配),所以不能允许p.data[j] = p.data[ next[j ]]。如果出现了p.data[j] = p.data[ next[j] ]咋办呢?如果出现了,则需要再次递归,即令next[j] = next[ next[j] ]。

优化后的next数组的求法如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] getNext(){
int next[] = new int[length];
next[0] = -1;

int j = 0, k = -1;
while(j < length-1){
//already knows next[j] = k, how to compute next[j+1]
if(k == -1 || data[j] == data[k]){
k++;
j++;
if(data[j] != data[k])
next[j] = k;
else
next[j] = next[k];
}else{
k = next[k];
}
}

return next;

}

利用优化过后的next 数组求法,可知模式串“abab”的新next数组为:-1 0 -1 0。下面这幅图揭示了KMP算法的实际执行过程。

KMP算法图示

上述部分图示和文字来源于 http://blog.csdn.net/v_july_v/article/details/7041827

KMP算法的时间复杂度

如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为O(n),算上计算next的O(m)时间,KMP的整体时间复杂度为$O(m + n)$。