《数据结构kmp》由会员分享，可在线阅读，更多相关《数据结构kmp（24页珍藏版）》请在金锄头文库上搜索。
1、KMP算法1. 朴素模式匹配算法(Brute-Force算法)求子串位置的定位函数Index( S, T, pos).l模式匹配：子串的定位操作通常称作串的模式匹配。 l目标串：主串S。 l模式串：子串T。 l匹配成功：若存在T的每个字符依次和S中的一个连续 字符序列相等，则称匹配成功。返回T中第一个字符在 S中的位置。 l匹配不成功：返回0。串的模式匹配算法KMP算法lBrute-Force简称为BF算法,亦称简单匹配算 法,其基本思路是:从目标串s=“s1s2sn“的第一个字符开始 和模式串t=“t1t2tm“中的第一个字符比较,若 相等,则继续逐个比较后续字符；否则从目标 串s的第二个字
2、符开始重新与模式串t的第一 个字符进行比较。依次类推,若从模式串s的 第i个字符开始,每个字符依次和目标串t中的 对应字符相等,则匹配成功,该算法返回i；否 则,匹配失败,函数返回0。KMP算法例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为 n(n=6),t的长度为m(m=3)。用指针i指示目标串s的当前比较 字符位置,用指针j指示模式串t的当前比较字符位置。BF模式 匹配过程如下所示。i = i j +2;j = 1;KMP算法l 子串定位int Index( SString S, SString T, int pos) i= pos; j = 1;while( iT0
3、) return i-T0;else return 0; KMP算法l 朴素模式匹配算法的时间复杂度主串长n； 子串长m。可能匹配成功的位置（1 n-m+1)。 最好的情况下，第i个位置匹配成功，比较了（i-1+m）次，平均比较次数 ：最好情况下算法的平均时间复杂度O(n+m)。 最坏的情况下，第i个位置匹配成功，比较了（i*m）次，平均比较次数：设nm，最坏情况下的平均时间复杂度为O(n*m)。KMP算法2. 模式匹配的改进算法-KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同 提出的,简称KMP算法。该算法较BF算法有较大改进,主 要是消除了主串指针的
4、回溯,从而使算法效率有了某种程 度的提高。因p1p2,s2=p2,必有s2p1,又因p1=p3,s3=p3,所 以必有s3=p1。因此,第二次匹配可直接从i=4, j=2开始。 KMP算法改进：每趟匹配过程中出现字符比较不等时，不回溯 主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。KMP算法s1 s2 s3si-j+1 si-j+2si-2 si-1 si si+1 p1 p2 pj-2 pj-1 pj pj+1 p1 pk-1 pk pk+1 “p1p2pk-1” = “si-k+1si-k+2si-1” “pj-k+1pj-k+2pj-1” = “s
5、i-k+1si-k+2si-1”（部分匹配） “p1p2pk-1” = “pj-k+1pj-k+2pj-1” (真子串）KMP算法max k|1T0) return i-T0; /*匹配成功*/else return 0; /*返回不匹配标志*/ KMP算法l 如何求next函数值 1. next1 = 0;表明主串从下一字符si+1起和模式串重 新开始匹配。i = i+1; j = 1; 2. 设nextj = k，则nextj+1 = ? 若pk=pj，则有“p1pk-1pk”=“pj-k+1pj-1pj” ，如果 在j+1发生不匹配，说明nextj+1 = k+1 = nextj+1。
6、若pkpj，可把求next值问题看成是一个模式匹配 问题，整个模式串既是主串，又是子串。KMP算法p1 p2pj-k+1pj-1 pj pj+1 nextj=k p1 pk-1 pk pk+1 nextk=kp1 pk pk+1 nextk=k”p1 pk pk+1 nextk=k l若pk=pj，则有“p1pk”=“pj-k+1pj”，nextj+1=k+1=nextk+1=nextnextj+1. l若pk”=pj ，则有“p1pk”=“pj-k”+1pj”，nextj+1=k”+1=nextk+1=nextnextk+1.lnextj+1=1.KMP算法j 1 2 3 4 5 6 7 8
7、 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 0nextj1 1 1 2 2 3 1 1 23 45 67 1 2KMP算法l void get_next(SString T, int next1 = 0; j = 0; while( iy THEN z: =x; ELSE z: =y; RETURN(z);END; KMP算法文本格式示例 KMP算法页页号起始位置长长度10107行号起始位置长度 1031 23115 3466 45221 57314 68714 71015页表行表KMP算法练习：(4.31)
8、以定长顺序存储结构表示串，设计一个 算法，求串s和串t的最长公共子串。 -3 -2 -1 0 1 2 3 4 5 6 7 8s1 s2 s3 s4 s5 s6 s7 s8 s9 t1 t2 t3 t4 t1 t2 t3 t4 t1 t2 t3 t41-T0 s0jmin=1;jmax=i+T0; /T有一部分在S左端的左边 jmin=i+1;jmax=i+T0; /T在S左右两端之间 jmin=i+1;jmax=S0;/T有一部分在S右端的右 边 KMP算法void Get_LPubSub(SStringS S, SString T) if(S0=T0) StrAssign(A,S); StrAssign(B,T); else StrAssign(A,T); StrAssign(B,S); for(maxlen=0,i=1-B0;iA0-B0) jmin=i+1; jmax=A0; else jmin=i+1; jmax=i+B0;for(k=0,j=jmin;jmaxlen) lps1=j-k+1; lps2=j-i-k+1; maxlen=k;
