当前位置:首页 >> 学科竞赛 >>

KMP


KMP算法

串的模式匹配算法
1. 朴素模式匹配算法(Brute-Force算法) 求子串位置的定位函数Index( S, T, pos). ?模式匹配:子串的定位操作通常称作串的模式匹配。 ?目标串:主串S。 ?模式串:子串T。 ?匹配成功:若存在T的每个字符依次和S中的一个连 续字符序列相等,则称匹配成功。返回T中第一个字符 在S中的位置。 ?

匹配不成功:返回0。

KMP算法

?Brute-Force简称为BF算法,亦称简单匹配算法, 其基本思路是: 从目标串s=“s1s2…sn"的第一个字符开始 和模式串t=“t1t2…tm"中的第一个字符比较,若 相等,则继续逐个比较后续字符;否则从目标 串s的第二个字符开始重新与模式串t的第一个 字符进行比较。依次类推,若从模式串s的第i个 字符开始,每个字符依次和目标串t中的对应字 符相等,则匹配成功,该算法返回i;否则,匹配失 败,函数返回0。

KMP算法

例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为 n(n=6),t的长度为m(m=3)。用指针i指示目标串s的当前比较 字符位置,用指针j指示模式串t的当前比较字符位置。BF模式 匹配过程如下所示。
第 1 次匹配 s=cddcdc t=cdc 第 2 次匹配 s=cddcdc t=cdc 第 3 次匹配 s=cddcdc t=cdc 第 4 次匹配 s=cddcdc t=cdc i=3 j=3 i=2 j=1 i=3 j=1 i=6 j=3 成功 失败 失败 失败

i = i –j +2;

j = 1;

KMP算法 ? 子串定位int Index( SString S, SString T, int pos) { i= pos; j = 1; while( i<=S[0] && j<=T[0]){ if(S[i] == T[j]){ ++i; ++j; } else{ i = i-j+2; j =1; } } if(j>T[0]) return i-T[0]; else return 0; }

KMP算法

? 朴素模式匹配算法的时间复杂度 主串长n; 子串长m。可能匹配成功的位置(1 ~ n-m+1)。 ①最好的情况下, 第i个位置匹配成功,比较了(i-1+m)次,平均比较次数: 最好情况下算法的平均时间复杂度O(n+m)。 ②最坏的情况下, 第i个位置匹配成功,比较了(i*m)次,平均比较次数: 设n>>m,最坏情况下的平均时间复杂度为O(n*m)。
n ? m ?1

?
i ?1

n ? m ?1 1 1 pi (i ? 1 ? m) ? ? (i ?1 ? m) ? 2 (m ? n) n ? m ? 1 i ?1 n ? m ?1 m 1 pi (i ? m) ? ? i ? 2 m(n ? m ? 2) n ? m ? 1 i ?1

n ? m ?1

?
i ?1

KMP算法

2. 模式匹配的改进算法-KMP算法 KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提 出的,简称KMP算法。该算法较BF算法有较大改进,主要 是消除了主串指针的回溯,从而使算法效率有了某种程度 的提高。
第 1 次匹配 s=abacaba b p=abab p=abab i=4 失败 j=4 j=2

因p1≠p2,s2=p2,必有s2≠p1,又因p1=p3,s3=p3, 所以必有s3=p1。因此,第二次匹配可直接从i=4, j=2开始。

KMP算法

改进:每趟匹配过程中出现字符比较不等时,不回溯 主指针i,利用已得到的“部分匹配”结果将模式向 右滑动尽可能远的一段距离,继续进行比较。

KMP算法

s1 s2 s3?si-j+1 si-j+2?si-2 si-1 si si+1
‖ ‖ ‖ ‖ ‖ ‖ ≠

p1

p2 ? pj-2 pj-1 pj pj+1

p1 ?

pk-1 pk pk+1

① “p1p2…pk-1” = “si-k+1si-k+2…si-1” ②“pj-k+1pj-k+2…pj-1” = “si-k+1si-k+2…si-1”(部分匹配) ③ “p1p2…pk-1” = “pj-k+1pj-k+2…pj-1” (真子串)

KMP算法

为此,定义next[j]函数,表明当模式中第j个字符与主 串中相应字符“失配”时,在模式中需重新和主串 中该字符进行比较的字符的位置。

max{ k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1” }

当此集合非空时
next[j]= 0 1 当j=1时 其他情况

KMP算法

int Index_KMP (SString S,SString T, int pos)
{ i= pos,j =1; while (i<S[0] && j<T[0]) { if (j==0 || S[i]==T[j]) { i++;j++; }

else
j=next[j]; } /*i不变,j后退*/

if (j>T[0]) return i-T[0]; /*匹配成功*/
else return 0; /*返回不匹配标志*/

}

KMP算法

? 如何求next函数值 1. next[1] = 0;表明主串从下一字符si+1起和模式串重新 开始匹配。i = i+1; j = 1; 2. 设next[j] = k,则next[j+1] = ? ①若pk=pj,则有“p1…pk-1pk”=“pj-k+1…pj-1pj” ,如果 在 j+1发生不匹配,说明next[j+1] = k+1 = next[j]+1。 ②若pk≠pj,可把求next值问题看成是一个模式匹配问 题,整个模式串既是主串,又是子串。

KMP算法

p1 p2?pj-k+1?pj-1 ‖ ‖ p1 ? pk-1 p1?? p 1?

pj pj+1 next[j]=k ≠ pk pk+1 next[k]=k’ pk’ pk’+1 next[k’]=k” pk’’ pk’’+1 next[k’’’]=k’’’

?若pk’=pj,则有“p1…pk’”=“pj-k’+1…pj”,

next[j+1]=k’+1=next[k]+1=next[next[j]]+1.
?若pk”=pj ,则有“p1…pk””=“pj-k”+1…pj”, next[j+1]=k”+1=next[k’]+1=next[next[k]]+1. ?next[j+1]=1.

KMP算法

j 模式串
next[j]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 a b c a a b b c a b c a a b d a b 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2

KMP算法 ? void get_next(SString T, int &next[]) { i= 1; next[1] = 0; j = 0; while( i<T[0]){ if(j==0 || T[i] == T[j]){ ++i; ++j; next[i] = j; } else j = next[j]; } }

KMP算法

?KMP算法的时间复杂度

设主串s的长度为n,模式串t长度为m,在KMP算
法中求next数组的时间复杂度为O(m),在后面的匹

配中因主串s的下标不减即不回溯,比较次数可记为
n,所以KMP算法总的时间复杂度为O(n+m)。

KMP算法

?next函数的改进
aaabaaaab
aaaa ① ② ③
j=4 j=3 j=2 j=1 i=4

j

12345

模式

aaaab

next[j] 0 1 2 3 4

aaa aa a

nextval[j] 0 0 0 0 4

aaaab i = 5; j = 1

next[j] = k,而pj=pk, 则 主串中si和pj不等时, 不需再和pk进行比较, 而直接和pnext[k]进行比 较。

KMP算法

j 模式串 next[j]
nextval[j]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 a b c a a b b c a b c a a b d a b 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1

KMP算法 ? void get_nextval(SString T, int &nextval[]) { i= 1; nextval[1] = 0; j = 0; while( i<T[0]){ if(j==0 || T[i] == T[j]){ ++i; ++j; if(T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; next[i] = j; } else j = nextval[j]; } }

KMP算法

串的应用举例:文本编辑
文本编辑程序用于源程序的输入和修改,公文书信、报

刊和书籍的编辑排版等。常用的文本编辑程序有Edit、WPS、
Word等。文本编辑的实质是修改字符数据的形式和格式, 虽然各个文本编辑程序的功能不同,但基本操作是一样的,

都包括串的查找、插入和删除等。 为了编辑方便,可以用分
页符和换行符将文本分为若干页,每页有若干行。我们把文 本当作一个字符串,称为文本串,页是文本串的子串,行是 页的子串。

KMP算法 采用堆存储结构来存储文本,同时设立页指针、行指针和 字符指针,分别指向当前操作的页、行和字符,同时建立页表

和行表存储每一页、每一行的起始位置和长度。 ?
假设有如下PASCAL源程序:
FUNC max(x, y: integer): integer;?

VAR z: integer;?
BEGIN? IF x>y THEN z: =x;?

ELSE z: =y;?
RETURN(z);? END;

KMP算法

文本格式示例

KMP算法 页表
页号 1 起始位置 0 长度 107

行表
行号 1 2 起始位置 0 31 长度 31 15

3
4 5

46
52 73

6
21 14

6
7

87
101

14
5

KMP算法

练习:(4.31)以定长顺序存储结构表示串,设计一个算 法,求串s和串t的最长公共子串。 -3 -2 -1 0 1 2 3 4 5 6 7 8

s1 s2 s3 s4 s5 s6 s7 s8 s9 t1 t2 t3 t4 t1 t2 t3 t4 t1 t2 t3 t4
1-T[0] s[0]

①jmin=1;jmax=i+T[0]; //T有一部分在S左端的左边 ②jmin=i+1;jmax=i+T[0]; //T在S左右两端之间 ③jmin=i+1;jmax=S[0];//T有一部分在S右端的右边

KMP算法
void Get_LPubSub(SStringS S, SString T) { if(S[0]>=T[0]) { StrAssign(A,S); StrAssign(B,T); } else { StrAssign(A,T); StrAssign(B,S); } for(maxlen=0,i=1-B[0];i<A[0];i++) { if(i<0) {jmin=1; jmax=i+B[0]; } else if(i>A[0]-B[0]) { jmin=i+1; jmax=A[0]; } else{ jmin=i+1; jmax=i+B[0];} for(k=0,j=jmin;j<=jmax;j++){ if(A[j]==B[j-i]) k++; else k=0; if(k>maxlen) {lps1=j-k+1; lps2=j-i-k+1; maxlen=k;} } } ………..; }


相关文章:
KMP算法详解
( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl; system("pause"); delete[] nextval; return 0; } main(...
KMP算法中next和nextval数组的求解
KMP算法中next和nextval数组的求解_计算机软件及应用_IT/计算机_专业资料。数据结构中KMP算法中求next和nextval数组的求解方法。intget_nextval(SStringT,int&nextval...
KMP播放器的简单使用方法
KMP 播放器的简单使用方法 KMPlayer 是一款来自韩国的影音全能播放器,与 Mplayer 一样从 linux 平台移植而来的 Kmplayer (简称 KMP)几乎可以播放您系统上所有的影音...
kmp算法详解_图文
引记此前一天,一位 MS 的朋友邀我一起去与他讨论快速排序,红黑树,字典树,B 树、后 缀树, 包括 KMP 算法, 唯独在讲解 KMP 算法的时候, 言语磕磕碰碰, ...
KMP和BF的区别
KMP和BF的区别_生物学_自然科学_专业资料。本文分为二个部分:第一部分、再次回顾普通的 BF 算法与 KMP 算法各自的时间复杂度, 并两相对照各自的匹配原理;第二部...
详解KMP算法中Next数组的求法
详解KMP 算法中 Next 数组的求法 例如: 1 2 3 4 5 6 7 8 模式串 next 值 a b a a b c a c 0 1 1 2 2 3 1 2 next 数组的求解方法是:第...
改进KMP算法
模式匹配的一种改进算法---KMP 算法 模式匹配的一种改进算法这种改进算法是 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发现的,因此人们称它为 克努特-莫里...
KMP串匹配并行算法的MPI实现
KMP 串匹配的 MPI 实现一、简单匹配算法 KMP 字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单 匹配算法的时间复杂度为 O(m*n);...
KMP配合终极解码搞定一切_图文
KMP配合终极解码搞定一切_计算机软件及应用_IT/计算机_专业资料。第一步 我们来确认一下什么是 720p,什么是 1080p,什么又是 1080i。我们说的高清到底是什么。 ...
KMP算法的核心思想
西安科技大学 上机报告 课程名称编译原理 专业计算机科学与技术 班级计算机科学与技术 1303 班 姓名 学号 张卫兵 1308030319 时间 2016 年 4 月 11 号 KMP 算法的...
更多相关标签:
kmplayer | kmp算法 | kmp播放器 | kmp官网 | kmplayer plus | kmp绿色版 | kmp算法详解 | potplayer |