模式匹配的KMP算法详解

模式匹配的KMP算法详解

模式匹配的KMP算法详解

模式匹配的KMP算法详解

这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法.大概学过信息学的都知道,是个比较难理解的算法,今天特把它搞个彻彻底底明明白白.

注意到这是一个改进的算法,所以有必要把原来的模式匹配算法拿出来,其实理解的关键就在这里,一般的匹配算法:

int Index(String S,String T,int pos)//参考《数据结构》中的程序 {

i=pos;j=1;//这里的串的第1个元素下标是1 while(iababc

这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在.这个当T[j]失配后,j应该往前跳的值就是j的next值,它是由T串本身固有决定的,与S串无关.

《数据结构》上给了next值的定义: 0 如果j=1

next[j]={Max{k|1aaab ->aaab

像这样的T,前面自身部分匹配的部分不止两个,那应该往前跳到第几个呢 最近的一个,也就是说尽可能的向右滑移最短的长度.

OK,了解到这里,就看清了KMP的大部分内容,然后关键的问题是如何求next值 先不管它,先看如何用它来进行匹配操作,也就是说先假设已经有了next值. 将最前面的程序改写成:

int Index_KMP(String S,String T,int pos) {

i=pos;j=1;//这里的串的第1个元素下标是1

while(i<=S.Length && jT.Length) return i-T.Length;//匹配成功 else return 0; }

OK,是不是非常简单 还有更简单的,求next值,这也是整个算法成功的关键,从next值的定义来求太恐怖了,怎么求 前面说过了,next值表达的就是T串的自身部分匹配的性质,那么,我只要将T串和T串自身来一次匹配就可以求出来了,这里的匹配过程不是从头一个一个匹配,而是从T[1]和T[2]开始匹配,给出算法如下:

void get_next(String T,int &next[]) {

i=1;j=0;next[1]=0; while(i<=T.Length) {

if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/} else j=next[j];

} }

看这个函数是不是非常像KMP匹配的函数,没错,它就是这么干的!注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的,j前面的都匹配的情况下,于是先自增,然后记下来next[i]=j,这样每当i有自增就会求得一个next[i],而j一定会小于等于i,于是对于已经求出来的next,可以继续求后面的next,而next[1]=0是已知,所以整个就这样递推的求出来了,方法非常巧妙.

这样的改进已经是很不错了,但算法还可以改进,注意到下面的匹配情况: ...aaac... aaaa.

T串中的'a'和S串中的'c'失配,而'a'的next值指的还是'a',那同样的比较还是会失配,而这样的比较是多余的,如果我事先知道,当T[i]==T[j],那next[i]就设为next[j],在求next值的时候就已经比较了,这样就可以去掉这样的多余的比较.于是稍加改进得到:

void get_nextval(String T,int &next[]) {

i=1;j=0;next[1]=0; while(i<=T.Length) {

if(j==0 || T[i]==T[j]) { ++i;++j;

if(T[i]!=T[j]) next[i]=j;

else next[i]=next[j];//消去多余的可能的比较,next再向前跳 }

else j=next[j]; } }

匹配算法不变.

到此就完全弄清楚了,以前老觉得KMP算法好神秘,真不是人想出来的,其实不然,它只不过是对原有的算法进行了改进.可见基础的经典的东西还是很重要,你有本事'废'了经典,就创造了进步.