浙大数据结构补充内容

课程地址:https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。

之前发现新的课程中补充了KMP算法,这里做下回顾。

串的模式匹配

串的模式匹配是找在文本中找到某个模式第一次出现的位置:

这里讨论的一般为字符串,设文本的长度为$n$,模式的长度为$m$,下面看下处理的方法。

蛮力算法

最基本的思路是蛮力算法,即让模式的头指针遍历文本的每个位置,然后比较后续对应位置的元素,不难看出,时间复杂度为$O(nm)$,这种时间复杂度是很难让人接受的,幸运的是,有人给出了KMP算法。

KMP算法

蛮力算法中模式的头指针一次只移动一个位置,那么这种操作能否改进呢?回答是肯定的,来看下面的例子:

为了讨论方便,这里引进两个新的变量$s,p$,$s$为文本当前匹配位置,$p$为模式当前匹配位置,通过移动$s,p$来进行匹配操作。图中$s$指向$x$,$p$指向$c$,因为$c\neq x$,所以指针要移动,蛮力算法是将$s$回退到第一个$b$的位置,$p$回退到模式的头指针位置,但是我们观察上图不难发现pattern的头部$ab$和$p$之前两位相同,所以我们可以保持$s$不动,将$p$指向第一个$c$的位置,于是就变为第三行的情形。这个例子提醒我们要先对模式串的模式进行分析,于是有了如下match数组:

有了match数组之后,匹配不成功回退的位置就可以知道了,令$i=\text{match}[p-1]$,那么$a_{0}…a_{i}$和$a_{p-i-1}…a_{p-1}$相同,所以$p$回退到$\text{match}[p-1]+1$的位置,可以结合下图看:

于是有了如下的算法:

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
typedef int Position;
#define NotFound -1

Position KMP( char *string, char *pattern )
{
//计算长度
int n = strlen(string);
int m = strlen(pattern);
Position s, p, *match;

//文本长度小于模式长度显然无法匹配
if ( n < m ) return NotFound;
match = (Position *)malloc(sizeof(Position) * m);
//构造match数组
BuildMatch(pattern, match);
//初始化指针
s = p = 0;
while ( s<n && p<m ) {
if ( string[s]==pattern[p] ) {
s++; p++;//相同则同时往后移动一位
}
else if (p>0) p = match[p-1]+1;//不相同且p不是头指针则回退
else s++;//否则s往后移动一个位置
}
return ( p==m )? (s-m) : NotFound;//p走到m表示匹配,返回其在文本中的位置,否则返回不匹配
}

接下来分析时间复杂度,计算长度的时间复杂度为$O(n+m)$,BuildMatch的时间复杂度暂时未知,设为$T_m$,最后循环的时间复杂度为$O(n+m)$,总的时间复杂度为$O(n+m+T_m)$,所以接下来的问题为如何快速BuildMatch

BuildMatch

BuildMatch相当于串的自匹配,结合下图讲解:

假设指针为$j$,令$i=\text{match}[j-1]$,那么$b_{0}…b_{i}$和$b_{j-i-1}…b_{j-1}$相同并且这种匹配是最大匹配,如果$b[i+1]$和$b[j]$相同,显然有

如果不同,则再往前回退,如下图:

不难看出$i$应该回退到$\text{match}[i]$的位置,然后继续比较$b[i+1]$和$b[j]$,继续回退直至相同或者无法回退为止,于是有了如下算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BuildMatch( char *pattern, int *match )
{
Position i, j;
int m = strlen(pattern);
match[0] = -1;

for ( j=1; j<m; j++ ) {
i = match[j-1];
while ( (i>=0) && (pattern[i+1]!=pattern[j]) )
i = match[i];//能回退且不相同则一直回退
if ( pattern[i+1]==pattern[j] )
match[j] = i+1;//相同则更新match
else match[j] = -1;//不能回退且不相同则为-1
}
}

接下来分析时间复杂度,老师讲解部分没有太听明白,查阅了网上资料,给出一个自己的分析过程。

不难看出,我们最主要分析的量为回退次数,假设$T[i]$为计算$\text{match}[i]$回退的次数,每次回退,$\text{match}[i]$至少减$1$,所以有如下不等式:

备注:注意一开始的赋值为

每次回退至少减少$1$,$T[i]$次回退至少减少$T[i]$,所以得到上述条件。

现在利用上述结论分析时间复杂度,计算长度的时间复杂度为$O(m)$,一共循环$m$次,每次最多增加$1$,总共最多回退$m$次,所以循环总共的时间复杂度为$O(m)$,因此BuildMatch的时间复杂度为$O(m)$,即$T_m =O(m)$,从而KMP算法的时间复杂度为$O(m+n)$