Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 字符串处理 » ,

KMP算法

字符串匹配是计算机中经典的问题:在一个很长的主字符串S中查找一个较短的模式串T,如果T在S中有出现,输出首次出现的下标,否则输出-1。
字符串匹配算法很多,本文主要讲解其中的KMP算法。KMP算法是一个高效的线性时间算法,其代码量不大,但理解稍有困难,需要细细体会。
以下所有例子及代码实现中,字符串下标均从0开始!

一 朴素算法

讲KMP算法必须先讲朴素的字符串匹配算法,朴素算法试图在主串S中的每个字符开始,比较这个字符开始的与T长度一样的子串是否跟T相同,如果不相同,则再比较下一个字符串开始的子串。
以下的例子中,假设S=oooabcaboabcabcoo,T=abcabc,我们用m表示S的长度,n表示T的长度,则m=17,n=6。

用i表示当前S串中访问的位置,j表示T串中访问的位置。显然,算法开始有i=0,j=0,如下绿色字符所示。

o o o a b c a b o a b c a b c o o
a b c a b c                      

经过一次比较,发现o!=a,于是以o开始的长度为6的子串肯定跟T不一样。于是可以考虑以第2个字符开始的子串,即i自增,而j仍保持为0(i++,j=0)。

o o o a b c a b o a b c a b c o o
  a b c a b c                    

比较发现,仍有o!=a,于是i再自增,j仍为0(i++,j=0)。仍是o!=a,于是i++,j=0。

o o o a b c a b o a b c a b c o o
      a b c a b c                

此时发现a==a,s[i]==t[j],这个位置匹配成功,于是可以把i和j各递增1(i++,j++),继续匹配两个字符串的下一个位置。递增之后还是匹配成功,于是再次将i、j递增,直到到达以下位置:

o o o a b c a b o a b c a b c o o
      a b c a b c                

此时有o!=c,匹配失败,于是要考虑下一个字符开始的子串。因为当前子串是下标为3的位置的字符a开始的子串,于是下一个要考虑下标为4的字符b开始id子串,这个5可以由i-(j-1)=9-(5-1)=5计算得到,而j只需重置为0,即i-=j-1,j=0。即得以下状态:

o o o a b c a b o a b c a b c o o
        a b c a b c              

重复以上的过程,一直匹配下去,直到模式串T匹配到了末端(如下图),此时匹配成功,找到了出现的位置,首个匹配位置可以由i-lt=14-6=10得到。

o o o a b c a b o a b c a b c o o
                  a b c a b c    

以上朴素算法的复杂度是O(m*n)。比如极端情况下S=aaa…ab(100000个a),T=aa..ab(10个a),S中找T大约需要比较100000*10次。
具体的代码实现如下:

//朴素字符串匹配算法
int match (char *s, char *t)
{
	int ls = strlen(s), lt = strlen(t), i = 0, j = 0;
	while (i<ls && j<lt)
	{
		if (s[i] == t[j])	i++, j++;
		else	{	i -= j - 1; j = 0;	}
	}
	if (j == lt)	return i - lt;
	return -1;
}

二 KMP算法

KMP算法是对朴素算法的一种改进,可以看到,朴素算法耗时的地方主要是i在对主串S遍历的时候,当出现不匹配时i的值要回溯到之前的某个值(代码中i-=j-1部分),极端情况下每个字符到要匹配n次,导致算法复杂度为O(m*n)。
KMP算法利用匹配失败时已匹配字符串的性质,保证在遍历时i不会进行回溯,于是i只会在S串中从头到尾扫一遍,保证了算法的线性性质。KMP算法的复杂度只有O(m+n)。

在如下状态匹配失败时,我们试图保持i不变,把子串T向右移若干个位置,即把j减少一定的值。

o o o a b c a b o a b c a b c o o
      a b c a b c                

在o这个位置匹配失败了,但我们知道之前的位置已经成功了,根据T串可知前面匹配成功的子串为abcab。如果我们把T向右移动一位,如下图

~ ~ ~ a b c a b ~ ~ ~ ~ ~ ~ ~ ~ ~
        a b c a b c              

此时肯定匹配失败,因为b!=a。同理,移动两位肯定匹配失败,因为c!=a。移动三位时,如下,

~ ~ ~ a b c a b ~ ~ ~ ~ ~ ~ ~ ~ ~
            a b c a b c          

匹配有可能成功,但还需继续后面的匹配。可以看到,此时ab这个子串是原来已匹配串abcab的前缀abcab,同时也是其后缀abcab,显然只有这样才可能继续匹配下去。于是,我们可以一次性把T串向右移动3个位置,而直接忽略不可能的移动方案(移动1格和2格)。这正是KMP算法高效的地方。

KMP算法有不同的实现方法,这里使用next数组。我们把“将T串向右移动3个位置”这样的动作表示为T的下标j的变化,比如上面例子中,当o!=c时(此时i=8,j=5),我们要将T串向右移动三个位置,于是变成i=8,j=2。这里记为next[5]=2,即如果T串在下标5匹配失败时,下次在下标next[5]=2上尝试匹配。
于是,如果有了next这个数组,我们在S遍历到i,T遍历到j时匹配失败时,只需进行j=next[j]即可进行下一次匹配。但可能多次进行j=next[j]一直到T串的头部也匹配失败,这时我们定义next[j]=-1,此时需要i自增以从S的下一个字符开始匹配,同时j需要置为0,这可以通过j自增得到。于是,无论是j=next[j]后得到了-1还是s[i]==t[j]匹配成功,我们都只需进行i++,j++的操作即可。

代码如下。

//KMP算法,s为文本串,t为模式串,s中找t
int kmp (char *s, char *t)
{
	int ls = strlen(s), lt = strlen(t);
	if (ls < lt)	return -1;
	int next[mx];	getNext(t, next);  //计算next数组
	int i = 0, j = 0;
	while (i<ls && j<lt)
		if (j==-1 || s[i]==t[j])	i++, j++;
		else	j = next[j];
	if (j >= lt)	return i - lt;
	return -1;
}

但关键是next数组是怎么计算出来的。next数组正是KMP算法的精华所在。

由上面可知,next[i]表示,当T串在位置i匹配失败时,下次匹配位置next[i]。考虑两次匹配时T的变化,如下,

0 1 2 3 i-next[i] i-next[i]+1 i-1 i
          0 1 next[i]-1 next[i]

这里要求T串中i位置前长度为next[i]的后缀和长度为next[i]的前缀必须相同,即t[0…next[i]-1]=t[i-next[i]…i-1],而且这相同的前后缀的长度必须是最大的,否则可能会漏掉某些匹配。
这可以看成是“第一个T串”和“第二个T串”的匹配,即T串自己和自己的KMP匹配。但这里第一个T串的位置是从1开始的,如下

a b c a b c  
  a b c a b c

显然当T的第0位都匹配失败时,我们只能把i自增,j置为0再重新匹配,即next[0]=-1(代码里显示给出)。
而当T的第1位匹配失败时,第0位满足前后缀相等的条件,即next[1]=0(代码里隐含确定)。

然后可以考虑上图,如果a==b(假如),那么当位置2上的c失配时,我们可以考虑位置1,即next[2]=1。但这里a!=b,于是令b=next[b]找出可能成功的匹配位置。
以下即是按照KMP算法的思路进行,具体根据代码理解。

//kmp算法 get Next数组
void getNext (char *t, int *next)
{
	int i = 0, j = -1, l = strlen(t);
	next[0] = -1;
	while (i < l)
		if (j==-1 || t[i]==t[j])	next[++i] = ++j; //注意++i和i++的区别
		else j = next[j];
}

求next数组时还有一个优化。

我们知道当T串第i位匹配失败时就去匹配第next[i]位,但如果T串中这两个位置的字符一样,再次匹配时还是失败,还是要做i=next[i]再匹配。如果现在的字符还是一样,那就再继续i=next[i],直到这一位匹配成功或i==-1为止。这里面t[i]==t[next[i]]时做的比较完全是没有必要的,我们可以在计算next数组时就避免这种比较。
具体就是代码中当我们准备做next[i]=j之前,我们先判断next[i]跟j是否相等,不相等的话才赋值,如果相等,我们就next[i]=next[j]。因为next[j]也是这样计算的,类似递归的思想,所以最终避免了i和next[i]上字符一样的问题。

代码如下:

//kmp算法 get Next数组(优化版)
void getNext (char *t, int *next)
{
	int i = 0, j = -1, l = strlen(t);
	next[0] = -1;
	while (i < l)
		if (j==-1 || t[i] == t[j])
		{
			i++, j++;
			if(t[i] != t[j])	next[i] = j;
			else	 next[i] = next[j];
		}
		else
			j = next[j];
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论