数据结构 第8讲 KMP算法

数据结构 第8讲 KMP算法

讲这个算法之前,我们首先了解几个概念:

串:又称字符串,是由零个或多个字符组成的有限序列。如S="abcdef"

子串:串中任意个连续的字符组成的子序列,称为该串的子串,原串称为子串的主串。如T="cde",TS的子串。子串在主串中的位置,用子串的第一个字符在主串中出现的位置表示。TS中的位置为3。

模式匹配:子串的定位运算称为串的模式匹配或串匹配。

假设有两个串ST,设S为主串,也称正文串,T为子串,也称为模式,在主串S中查找与模式T相匹配的子串,如果查找成功,返回匹配的子串第一个字符在主串中的位置。

最笨的办法就是穷举所有S的所有子串,判断是否与T匹配。

例如:S="abaabaabeca",T=" abaabe",求子串T在主串S中的位置。

S串第1个字符开始:i=1,j=1,比较两个字符是否相等,如果相等,则i++,j++;如果不等则执行第2步;

S串第2个字符开始:即i退回到i-j+2的位置,即i=2,j=1,比较两个字符是否相等,如果相等,则i++,j++;如果不等则执行第3步;

S串第3个字符开始:即i退回到i-j+2的位置,即i=3,j=1,比较两个字符是否相等,如果相等,则i++,j++;如果不等则执行第4步;

S串第4个字符开始:即i退回到i-j+2的位置,即i=4,j=1,比较两个字符是否相等,如果相等,则i++,j++;此时T串比较完了,执行第5步;

需要返回子串在主串S中第一个字符出现的位置,即i-m=10-6=4,mT串的长度。

上述算法称为BF(Brute Force)算法,Brute Force的意思是蛮力,暴力穷举。其时间复杂度最坏达到O(n*m),nm分别为S、T串的长度。

实际上,完全没必要从S的每一个字符开始,暴力穷举每一种情况,Knuth、Morris和Pratt对该算法进行了改进,称为KMP算法。

我们再回头看刚才的例子:

S串第1个字符开始:i=1,j=1,比较两个字符是否相等,如果相等,则i++,j++;按照BP算法,如果不等则i退回到i-j+2的位置,即i=2,j=1。

其实i不用回退,让j回退到第3个位置,接着比较即可。

是不是像T串向右滑动了一段距离?

为什么可以这样?为什么让j回退到第3个位置?而不是第2个?第四个?

因为T串中开头的两个字符和i指向的字符前面的两个字符一模一样噢,那j就可以回退到第3个位置继续比较了,因为前面两个字符已经相等了。

那我们怎么知道T串中开头的两个字符和i指向的字符前面的两个字符一模一样?难道还要比较?我们发现i指向的字符前面的两个字符和T串中j指向的字符前面两个字符一模一样,因为它们一直相等,才会i++,j++走到后面的位置。

也就是说,我们不必判断T串中开头的两个字母和i指向的字符前面的两个字符是否一样,只需要在T串本身比较就可以了。即T′的前缀和T′的后缀比较即可:

判断T′="abaab"的前缀和后缀是否相等,找相等前缀后缀的最大长度。

长度为1的:前缀"a",后缀:"b",不等×

长度为2的:前缀"ab",后缀:"ab",相等√

长度为3的:前缀"aba",后缀:"aab",不等×

长度为4的:前缀"abaa",后缀:"baab",不等×

注意:前缀和后缀不可以取字符串本身。串的长度为5,前缀和后缀长度最多达到4。

相等前缀后缀的最大长度为l=2,则j就可以回退到第l+1=3个位置继续比较了。

现在我们可以写出通用公式,next[j]表示j可以回退的位置,T′="t1t2…tj-1",则:

那么我们很容易求出T="abaabe"的next[]数组:

解释:

j=1:根据公式next[1]=0;

j=2:T′="a",没有前缀和后缀,next[2]=1;

j=3:T′="ab",前缀为"a",后缀为"b",不等,next[3]=1;

j=4:T′="aba",前缀为"a",后缀为"a",相等且l=1;前缀为"ab",后缀为"ba",不等,next[4]=l+1=2;

j=5:T′="abaa",前缀为"a",后缀为"a",相等且l=1;前缀为"ab",后缀为"aa",不等;前缀为"aba",后缀为"baa",不等,因此next[5]=l+1=2;

j=6:T′="abaab",前缀为"a",后缀为"b",不等;前缀为"ab",后缀为"ab",相等且l=2;前缀为"aba",后缀为"aab",不等;前缀为"abaa",后缀为"baab",不等,取最大长度2,因此next[6]=l+1=3。

这样找所有的前缀和后缀比较,是不是也是暴力穷举?

那怎么办呢?Look……

用动态规划递推一下:

首先大胆假设,我们已经知道了next[j]=k,即:

那么next[j+1]=?

考察以下两种情况:

tk=tj:那么next[j+1]=k+1,即相等前缀和后缀的长度比next[j]多1。

tktj:当两者不相等时,我们又开始了这两个串的模式匹配,找next[k]的位置tk′与tj比较,程序中的处理,只需要把next[k]赋值给k,即k←next[k],然后再比较tktj是否相等,如果相等则next[j+1]=k+1;

如果不相等,则继续向前找next[k′],如果不相等,继续向前找,直到找到next[1]=0,停止,此时next[j+1]=0+1=1,即从第一个字符开始。

求解next[]的代码实现如下:

void get_next(SString T, int next[]) //求模式串T的next函数值

{

int j=1, k= 0;

next[1] = 0;

while (j

if (k== 0 || T[j] ==T[k])

next[++j]=++k;

else

k= next[k];

}

用上述方法再次求解求出T="abaabe"的next[]数组:

解释:

1.初始化时next[1]=0,j=1,k=0,进入循环,判断满足k==0,则执行next[++j]=++k,即next[2]=1,此时j=2,k=1

2.进入循环,判断满足T[j]==T[k],T[2]≠T[1],则执行k=next[k],即k=next[1]=0,此时j=2,k=0

3.进入循环,判断满足k==0,则执行next[++j]=++k,即next[3]=1,此时j=3,k=1

4.进入循环,判断满足T[j]==T[k],T[3]=T[1],则执行next[++j]=++k,即next[4]=2,此时j=4,k=2

5.进入循环,判断满足T[j]==T[k],T[4]≠T[2],则执行k=next[k],即k=next[2]=1,此时j=4,k=1

6.进入循环,判断满足T[j]==T[k],T[4]=T[1],则执行next[++j]=++k,即next[5]=2,此时j=5,k=2

7.进入循环,判断满足T[j]==T[k],T[5]=T[2],则执行next[++j]=++k,即next[6]=3,此时j=6,k=3

8.j=T[0],循环结束。

结果是不是和穷举前缀后缀一模一样?

有了next[]数组,就很容易进行模式匹配了,当S[i]≠T[j]时,j退回到next[j]的位置继续比较即可。

这样求解非常方便,迅速,但是也发现有一个问题:当S[i]≠T[j]时,j退回到next[j],然后S[i]与T[k]比较。这样的确没错,但是如果T[k]=T[j],这次比较就没必要了,因为我们刚知道S[i]≠T[j]啊,那么肯定S[i]≠T[k],完全没必要再比了。

再向前找下一个next[],即找next[k]的位置,继续比较就可以了。本来应该和第k个位置比较呢,相当于跳到了k的下一个位置。减少了一次无效比较。

修改程序:

求解next[]的改进代码实现如下:

void get_next2(SString T, int next[]) //求模式串T的next函数值

{

int j=1, k= 0;

next[1] = 0;

while (j

{

if(k==0||T[j]==T[k])

{

j++;

k++;

if(T[j]==T[k])

next[j]=next[k]; //调到k的下一个位置,即next[k]

else

next[j]=k;

}

else

k=next[k];

}

完美~~~

/***KMP及改进算法***/

#include

#include

using namespace std;

#define Maxsize 100

typedef char SString[Maxsize+1];        //0号单元存放串的长度

bool StrAssign(SString &T, char *chars)//生成一个其值等于chars的串T

{

int i;

if (strlen(chars)>Maxsize)

return false;

else

{

T[0]=strlen(chars);

for(i=1; i<=T[0]; i++)

{

T[i]=*(chars+i-1);

cout<

}

cout<

return true;

}

}

void get_next(SString T, int next[])//计算next函数值

{

int j=1,k=0;

next[1]=0;

while(j

{

if(k==0||T[j]==T[k])

next[++j]=++k;

else

k=next[k];

}

cout<<"-----next[]-------"<

for(j=1;j<=T[0];j++)

cout<

cout<

}

void get_next2(SString T, int next[])//计算next函数值改进算法

{

int j=1,k=0;

next[1]=0;

while(j

{

if(k==0||T[j]==T[k])

{

j++;

k++;

if(T[j]==T[k])

next[j]=next[k];

else

next[j]=k;

}

else

k=next[k];

}

cout<<"-----next[]-------"<

for(j=1;j<=T[0];j++)

cout<

cout<

}

int Index_KMP(SString S, SString T, int pos, int next[])//KMP算法

{     //利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法

//其中,T非空,1≤pos≤StrLength(S)

int i=pos, j=1,sum=0;

while (i<=S[0] && j<=T[0])

{

sum++;

if (j==0||S[i]==T[j])  //继续比较后面的字符

{

i++;

j++;

}

else

j=next[j]; //模式串向右移动

}

cout<<"一共比较了"<

if (j>T[0]) //匹配成功

return i-T[0];

else

return 0;

}

int main()

{

SString S,T;

cout<<"串S:"<<" ";

StrAssign(S,"aabaaabaaaabea");

cout<<"串T:"<<" ";

StrAssign(T,"aaaab");

int *p=new int[T[0]+1]; //生成T的next数组

cout<

cout<<"KMP算法运行结果:"<

get_next(T,p);

cout<<"主串和子串在第"<

cout<

cout<<"改进的KMP算法运行结果:"<

get_next2(T,p);

cout<<"主串和子串在第"<

return 0;

}

版权声明:本文为博主原创文章,未经博主允许不得转载。博客原文地址http://blog.csdn.net/rainchxy/article/details/78130155

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容