KMP算法(原创).ppt

《KMP算法(原创).ppt》由会员分享，可在线阅读，更多相关《KMP算法(原创).ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、简单算法(Brute-Force算法算法)n算法描述：n从正文s和模式p的第一个字符出发，将s和p的字符依次逐个进行比较，如果p中的所有字符均与s中的对应字符匹配，则说明匹配成功；如果在比较过程中发现了一个字符不匹配，则将模式p沿正文s向后移动一个字符的位置，然后再从p的第一个字符开始与中的对应字符逐个进行比较。以此类推，直到匹配成功或到达的末段为止。(2) Brute-Force(2) Brute-Force算法的实现算法的实现 int String:Find Substr(const String& t, int start)constint i = start, j = 0, v;whi

2、le(i size & j = t.size-1) v = i-t.size+1;else v = -1;return v; 模式匹配的KMP算法n基本思想：n当模式p与正文s进行比较的过程中发现不匹配时，找到一种模式p沿正文s向后移动的规则，以便使得正文s中失去匹配的字符以前的字符不再参与比较，即只从当前失去匹配的字符开始与模式p中的字符继续依次进行比较，并且又不错过模式被发现的机会。n示例：算法分析n假设正文为s0s1sn-1，模式为p0p1pm-1，要实现改进算法，也就是要解决下述问题：当匹配过程中产生失配时(即si != pj)，模式“向右滑动”可行的距离有多远，换句话说，当正文中第i

3、个字符与模式中第j个字符“失配”时，正文中第i个字符应与模式中哪个字符相比较？n假设此时应与模式中第k个字符继续比较，其中k应具有以下两个性质：n1、kj，因为当失配时必然使模式p向后移，从而导致kj。移的幅度越小，k与j相差越小。n2、k应取所有可能值可能值中的最大值，因为取最大值就意味着移的幅度最小，也就避免错过成功匹配的机会。n根据这个假设，必然使得下式成立：np0p1pk-1=si-ksi-k+1si-1 (1)n而已经得到的“部分匹配”的结果是：npj-kpj-k+1pj-1=si-ksi-k+1si-1n (2)n(2)式的由来是：n 当初正文中的第i个字符与模式中的第j个字符失配

4、时，说明两者之前的j个字符肯定是一样的，而kj，所以前k个字符也是相同的。这就得出(2)式。n由(1)(2)两式便可得：np0p1pk-1= pj-kpj-k+1pj-1 (3)n(3)式的结论可如下描述：n在模式p中，前k个字符与第j个字符之前的k个字符相同。n设nextj表示：当模式中第j个字符与正文中相应字符“失配”时，在模式中重新和正文中该字符进行比较的字符的位置。n并令nextj=k。nNext数组的完整定义如下：Max k | 0kk满足上式，那么n nextj+1=k+1 式式1n也就是：nextj+1=nextj+1n2、若pk!=pj，则表明p0p1pk ! = pj-kpj

5、-k+1pjn这时如何求nextj+1呢？有两种可能情况转化法n式式1的结论结论可这样描述：何时的k使得pk=pj，就用此时的k代入式1。n而现在的k是pk!=pj，因此必须要换成另外一个“k”，并设它为k2，以使得pk2=pj。n问题又出来了： k2如何得来？n如图：要使得k转为k2，实际上就是将p往右移，移动后p的j对应p的k2。00jjj-k+1kPPnk k2 2，到底是多少首先取决于另一个前提条件前提条件：np0p1pk2-1= pj-k2pj-k2+1pj-1n如图：n实际上，n k2=nextk000jjjj-k+1kkk2k- k2 +1p1p2p3 那么，满足了这个前提条件，是否就满足pk2=pj了呢？ 显然两者互不相干。也就是说，仅移动一次不一定满足pk2=pj 。 如果移动一次后得到k2仍然不满足pk2=pj ，就要按照前提条件再移动一次。 依次类推，直到pkn=pj ,或kn=0为止。 此时有： nextj+1= kn +1 而 kn = nextkn-1 k1 =k= nextjn由于， kn kn-1 k1 =kj n因此，当需要求nextj+1时， nextj、 nextk1、 nextk2 nextkn都已经求出来了。