1. 传统字符串匹配机制

KMP是对字符串匹配优化的算法,要了解kmp算法由来应先了解传统的字符串匹配的工作机制

传统的字符串匹配机制如下:

有两个字符串,上面那个是主串(T),下面那个是模式串(相当于关键字,下面称为p)

要在T中查找是否含有p,我们要做的工作自然是在T和p之间各自定义一个哨兵i和j,各自一位一位比对,如下图 如果i和j所指的值都相同,那么两者都往前走,若是不同,如下图 此时AE不等,这时候i和j都需要回溯,i要从之前的第3位返回到第1位,j要从第3位返回到第0位,如图

然后重复上述比较过程,这就是传统的字符串匹配过程.

传统字符串匹配的缺点

若匹配到不等的情况时,i和j都要回溯,这样一来重复无意义的比较次数很多,导致整个算法效率低下

2.KMP算法的匹配机制

在这种情况下,主角KMP要出场了,KMP比传统字符串匹配的优秀之处就是保证i不回溯,一直勇往直前,而努力考虑匹配不成功时,j最佳的回溯位置,以此尽量减少重复无意义的比较

而KMP最精彩也是最难以理解的部分就是j最佳回溯位置的确定,

1. T和P匹配成功:不管是传统的还是在kmp中,只要匹配成功都是i和j同时加1,往前走
2. T和P匹配失败(整个KMP的优化工作全在这体现):此时保证i不回溯,j回溯到事先确定得到的最佳回溯位置next[j],即模式串中到j下标时,T[i]!=P[j],则i不动,j回溯到next[j]位置,然后再来比较T[i]和P[next[j]]的值

那么怎么得到保存了匹配失败时j 的最佳回溯位置的next[]数组呢

如图,我们先来找规律,此时c和d不相等

若是个聪明人就会做如下的比较,而不是i和j都回0位置 下图也是如此

i不动,j回溯到第2位

同志们,看到这里就又回到中学时期,根据给出的有限的两种图找出j位置的一般性规律了

##j位置的一般性规律如下图## 图中k,即为当i和j匹配失败时,j最佳的回溯位置

• 值得强调的是:next数组只和模式串p有关,跟主串没半毛钱关系

• j回溯位置k的描述

  p[0~k-1]==p[j-k~j-1]

k的位置要满足这样一个特性,即p[0~k-1]的序列要和p[j-k~j-1]的序列完全相同,白话文就是,p序列从0位置到k-1位置之间共k个字符的序列要和j前面k个序列相等

• 讲了这么多next数组,但一定要记住**next数组的值就是当i和j匹配失败时,j下一步要回到的位置(即为next[j])**

3. KMP代码

#include <iostream>
#define maxSize 100
void getNext(char ch[],int n,int *next){//得到next数组 
	int j,k;//next数组的作用就是当模式串和主串在模式串j位置不匹配时,j应回溯到next[j] 
	j=0;k=-1;
	next[0]=-1;
	while(j<n-1){
		if(k==-1||ch[j]==ch[k]){
			k++;
			j++;
			next[j]=k;
		}else{
			k=next[k];
		}
	}
} 
int KMP(char ch[],int n,char p[],int m){
	int i,j;
	i=j=0;
	int next[maxSize];
	getNext(ch,n,next);
	while(i<m&&j<n){
		if(j==-1||ch[j]==p[i]){//next[0]=-1; 下标为0的位置,模式串指针不能再往左移了 
			i++;
			j++;
		}else{
			j=next[j];
		}
	}
	if(j==n){//最后若是匹配成功,j和i都是为各自的字符串长度 
		return i-j;//返回的是主串开始匹配的位置 
	}else{
		return -1;
	}
	
}
int main(int argc, char** argv) {
	char p[]={'a','c','a','b','b','e'};
	char ch[]={'b','b'};
	int result=KMP(ch,2,p,6);
	printf("%d",result);
	return 0;
}

4.代码解析

以上代码很简洁有木有,但getNext函数部分依旧晦涩的很,以下用图来剖析他的意图

i和j匹配失败,按道理应该i不动,回溯j,但j左边没有值了,只能是i向右走一步,所以才有next[0]=-1的初始化

那要是j=1处匹配失败呢?自然,j只能回到0位置,别无可选

一般情况下,若p[k]==p[j](对应代码第8行情况) 此时可发现规律:(对应代码第9~11行)

当p[k]==p[j]时,next[j+1]==next[j]+1

不信看下图

当p[k]!=p[j]时(代码见12行),如下图 此时代码给出的回应是(见代码13行) k=next[k] 怎么理解这段代码?看下图

这里是整段代码中最难理解部分,给出如下阐述

为了描述方便,把上面那串叫A,下面的串叫B, 不管p[k]与p[j]是否相等,p[0~k-1]==p[j-k~j-1],即A[0~j-1]==B[0~k-1]都成立,若是p[k]==p[j],那么k和j之前会拥有最长的前缀串p[0~k-1](即B[0~k-1]),但由于p[k]!=p[j],于是乎,为了下一步的匹配,要在这最长的前缀串中砍掉几个,得到尽可能长的新前缀串,而next[k]表示p[0~t]==p[k-t~k-1](即B[0~t]==B[k-t~k-1]),即B串的前面的t个序列和从0开始的t个序列相同(t<k),而next[j]的存在早说明了A[0~j-1]==B[0~k-1],所以啊,通过等价代换可知B[0~t]=B[k-t~k-1]=A[j-t~j-1],即新的最长前缀串为B[0~t],所以k=next[k]

至此,代码中next数组的生成函数getNext的工作原理我们讲完了,KMP函数自然是小菜一碟了

##注:此篇文章除小部分总结,其他都是借鉴孤~影大神博文##