KMP

定义

一种由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人设计的线性时间字元串匹配算法。这个算法不用计算变迁函式δ，匹配时间为Θ（n），只用到辅助函式π[1，m]，它是在Θ（m）时间内，根据模式预先计算出来的。数组π使得我们可以按需要，“现场”有效的计算（在平摊意义上来说）变迁函式δ。粗略地说，对任意状态q=0，1，…，m和任意字元a∈Σ，π[q]的值包含了与a无关但在计算δ（q，a）时需要的信息。由于数组π只有m个元素，而δ有Θ（m∣Σ∣）个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。

伪代码

KMP-MATCHER(T，P)n←length[T]m←length[P]π←COMPUTE-PREFIX-FUNCTION(P)q←0　//Numberofcharactersmatched.fori←1ton　//Scanthetextfromlefttoright.dowhileq>0andP[q+1]≠T[i]doq←π[q]　//Nextcharacterdoesnotmatch.ifP[q+1]=T[i]thenq←q+1　//Nextcharactermatches.ifq=m　//IsallofPmatched?thenprint"Patternoccurswithshift"i-mq←π[q]　//Lookforthenextmatch.COMPUTE-PERFIX-FUNCTION(P)m←length[P]π[1]←0k←0forq←2tomdowhilek>0andP[k+1]≠P[q]dok←π[k]ifP[k+1]=P[q]thenk←k+1π[q]←kreturnπ

Python代码

defprefix(str):m=len(str)pi=[0foriinrange(m)]pi[0]=0k=0forqinrange(1,m):whilek>0andstr[k]!=str[q]:k=pi[k-1]ifstr[k]==str[q]:k=k+1pi[q]=kreturnpidefmatch(t,p):n=len(t)m=len(p)pi=prefix(p)q=0foriinrange(0,n):whileq>0andp[q]!=t[i]:q=pi[q-1]ifp[q]==t[i]:q=q+1ifq==m:print("matchedin%d.n"%(i-m+1))print("notmatched!n")

详细阐述

next数组的理解与计算

首先声明在不同的地方对next数组的定义和计算有所不同，为了避免混淆，在此仅介绍一种。next数组是对于模式字元串也就是需要被匹配字元串其中的每一个字母而言，为了在匹配时避免重複判断而存在，下面通过一个实例来介绍next数组的意义和具体用法。首先摆出next数组a 匹配串：b a b a b b；0 0 1 2 3 1；列如 s原串：b a b a b a b c b a b a b a b a b b；a匹配串：b a b a b b；先按暴力匹配可以得到如下原串：b a b a b a bcb a b a b a b a b b；匹配串 b a bab b；在如图黑色字母处出现不匹配，如果继续暴力，则会将匹配串向后移一位，然后再重新将匹配串的指针指向首位重新开始逐个匹配。但现在思考一下，我已经匹配了过了前三个字元了，可不可以合理地利用已知的条件呢？next数组就起到了运用已知条件的作用。如next[2]=1（从0开始），代表从匹配串队首开始向后走1（包括此点）与从a[2]开始向前走1的字元串完全相同。如next[3]=2,代表a[0],a[1]所组成的字元串与a[2]a[3]组成的完全相同。next[n]就代表n满足上述条件的长度。这样的话next数组的求解就十分容易了，只需o（n）的複杂度；next[0]必为0，对于求解next[n]，採用递推思想，如果next[n]=k;(k>0)则必须next[n-1]=k-1;如果next[n-1]=0;则看next[n]是否等于next[0]。如等于则next[n]=1。接下来就是实现时next数组的现实作用了，如上图，设原串的指针为i，匹配串的指针为j。当匹配到a[3]失败时，要注意因为从a[j]即a[3]开始向前走next[j-1]，即1与从队首开始向后走next[j-1]的字元是相同的，所以j回到next[j-1]，即a[1]的位置，而i指针不变，再进行比较。这样就能高效地进行匹配。

结合图像来看，如右下图加黑的B与A部分就是匹配失败时next[j-1]的值代表B部分与A部分完全相同，所以直接跳过这部分，直接将j指针移到A部分的后一位处，即next[j-1]处。

C示例代码

//c++实现的KMP算法，所有涉及字元串，其初始下标从0开始（上述算法均是从1开始）//example:chars[100],t[100];cin>>s>>t;KMP(s,t);//获取待查询模式的next数组int*get_next(char*T,int*next){int i=0,j=-1;int length=strlen(T);int *temp=next;    *next=-1;    while(i<length)    {        if(j==-1||*(T+i)==*(T+j))        {            i++;            j++;//最佳化后的get_next方法，可以防止出现形如"aaaaab"这种模式的计算退化            if(*(T+i)!=*(T+j))                *(next+i)=j;            else                *(next+i)=*(next+j);        }        else            j=*(next+j);    }    return temp;}//KMP算法intKMP(char*S,char*T){int S_Length=strlen(S);int T_Length=strlen(T);//若模式长度大于字元串，则直接返回查询失败if(S_Length<T_Length)    return 0;int i=0,j=0;int *next=newint[T_Length];    get_next(T,next);    while(i<S_Length&&j<T_Length)    {        if(j==-1||*(S+i)==*(T+j))        {            i++;            j++;        }        else            j=*(next+j);    }    if(j>=T_Length)        return i-T_Length;    return 0;}

在此提供一个更简明的适用于字元串的kmp实现：

#include<iostream>#include<string.h>intnext[100];voidgetnext(charb[]){inti=1,j=0;//i是每个位子，j是回退的位子next[1]=0;while(i<=strlen(b)){if(j==0||b[i-1]==b[j-1]){i++;j++;next[i]=j;}elsej=next[j];//用上一个的回退关係}}intkmp(chara[],charb[]){inti=1,j=1;//i是主串中的位子，j匹配串的位子while(i<=strlen(a)&&j<=strlen(b)){if(j==0||a[i-1]==b[j-1]){i++;j++;}elsej=next[j];}if(j>strlen(b))returni-strlen(b);elsereturn0;}intmain(){chara[40],b[40];printf("要匹配的主串：n");scanf("%s",a);printf("要匹配的目标字元串：n");scanf("%s",b);getnext(b);printf("输出next值：n");for(inti=1;i<=strlen(b);i++)printf("%d",next[i]);printf("n");printf("%d",kmp(a,b));system("pause");main();return0;}

C示例改进过程

根据题设，程式可写成：

voidGetNext(char*T,int*next){intk=1,j=0;next[1]=0;while(k<T[0]){if(j==0||T[k]==T[j]){++k;++j;next[k]=j;}elsej=next[j];}}

但是这个不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法複杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：

voidGetNextEx(char*T,int*next){intk=1,j=0;next[1]=0;while(k<strlen(T)){if(j==0||T[k]==T[j]){++k;++j;if(T[k]==T[j])next[k]=next[j];elsenext[k]=j;}elsej=next[j];}}

现在我们已经可以得到这个next字元串的值了，接下来就是KMP算法的本体了：相当简单：

intKMP(char*S,char*T,intpos){intk=pos,j=1;inttt=strlen(S);while(k<tt){if(S[k]==T[j]){++k;++j;}elsej=next[j];}if(j>T[0])returnk-T[0];elsereturn0;}

和朴素算法相比，只是修改一句话而已，但是算法複杂度从O(m*n) 变成了：O(m+n)对比

//findatemplateinastring.#include<string.h>#include<stdio.h>intIndex(char*S,char*T,intpos)//pos记录从哪一位开始匹配可以直接用0代替{intk=pos,j=0;while(k<strlen(S)&&j<strlen(T))//未超出字元串的长度{if(S[k+j]==T[j])++j;//如果相同，则继续向后比较else{k++;j=0;}//如果不同，就回溯，重新查找}if(j==strlen(T))returnk；elsereturn0;}

实际套用

用KMP算法，计算串的最大匹配论文

摘要

给定两个串S和T，长分别m和n，本文给出了一个找出二串间最大匹配的算法。该算法可用于比较两个串S和T的相似程度，它与串的模式匹配有别。

关键字

模式匹配 串的最大匹配 算法Algorithm on Maximal Matching of StringsLin YuCai Xiang YongHong Zhang ChunXia Zhang JianJun（Computer Science Department of Yunnan Normal University Kunming 650092）ABSTRACT Given Two Strings S of length m and T of length n，the paper presents an algorithm which finds the maximal matching of them. The algorithm can be used to compare the similarility of the two strings S and T,it is different with the strings' pattren matching.KEY WORDS Pattern Matching Maximal Matching of Strings Algorithm

提出问题

字元串的模式匹配主要用于文本处理，例如文本编辑。文本数据的存储（文本压缩）和数据检索系统。所谓字元串的模式匹配[2]，就是给定两个字元串S和T，长度分别为m和n，找出T中出现的一个或多个或所有的S，在这方面已经取得了不少进展。本文从文本处理的另一个角度出发，找出两个串的最大匹配，比较其相似程度。它主要套用于文本比较，特别是在计算机辅助教学中。显然前者要找S的完全匹配，而后者并无此要求。例如，若S=ABCD，T=EFABCDX，那幺模式匹配的结果就是找出了T中的一个ABCD，而我们算法的结果就是S能与T的ABCD完全匹配，但是T中还有3个字元是比S多出来的，也就是说在S中有100%的字元与T中的匹配，而在T中有57%的字元与S中的匹配。若S= ABCDFE，T=AFXBECDY。则在模式匹配中S与T无匹配项，但在我们的算法中就能发现T中存在A，B，C，D，但D后不存在E，F。而且S中也存在A，B，C，D，且具有顺序性。这样就能公正地评价S，T的区别。得知其相似程度。文章的组织如下：首先介绍基本定义和问题的描述；第三节是算法设计；最后是本文总结。

问题描述

设∑为任意有限集，其元称为字元，w：∑→N为∑到N的函式，称为∑的权函式（注：本文仅讨论权值恆为1的情况）。∑*为∑上的有限字元串集合，那幺对任意S，T∈∑*，设S=a1a2…am，T=b1b2…bn，m>0，n>0。记<m>={1,2，…，m},<n>={1,2，…，n}，则称{(i,j）∣i∈<m>；，j∈<n>；，ai=bj}为S与T的匹配关係集，记作M（S，T），称M为S与T的一个（容许）匹配，若对任意（i,j），（i',j'）∈，① i< i'，若且唯若j< j'，② i= i'若且唯若j= j'。S与T的匹配中满足 最大者，称为S与T的最大匹配。若C(i,j）为N上的m×n矩阵，且满足：
则称矩阵C为串S与T的匹配关係阵。于是求串S与T的最大匹配，等价于求C中的一个最大独立点集M，它满足，若ci,j，ci',j'∈M，则i< i' 若且唯若j< j'，i=i'若且唯若j=j'。我们称这样的最大独立点集为C的最大C-独立点集。例：设∑为所有字母的集合，对任意x∈∑，w（x）≡1，设S与T分别为：S=“BOOKNEWS”，T=“NEWBOOKS”。则我们可以得到S与T两个匹配：这里=5；这里 =4。显然为串S与T的最大匹配。S与T的匹配关係阵C可表示如下：其中带圈的部分为一最大C-独立点集。设计我们仅就权值为一的情况进行讨论。设S和T为任意给定串，C为的S与T匹配关係阵，那幺由2的讨论知，求S与T的最大匹配问题，等价于求C的最大C-独立点集问题。因而，为了解决我们的问题，只要给出求C的最大C-独立点集的算法就可以了。显然，为了求出C的最大C-独立点集，我们可以採用这样的方法：搜寻C的所有C-独立点集，并找出它的最大者。这种方法是可行的，但并不是非常有效的。这会使问题变得很繁，複杂度很大。因此，我们先对问题进行分析。在下面的讨论中，我们把C的任一C-独立点集={ai1,j1，…，ais,js}，记作=ai1,j1…ais,js，i1 <；…< is。于是可看作阵C中以1为节点的一条路，满足：对路中的任意两节点，均有某一节点位于另一节点的右下方。称这种路为右下行路。于是求C-独立点集等价于求阵C的右下行路。这种求右下行路的搜寻可以逐行往下进行。命题1. 若 =αai,jβ和ψ=α'ai,jσ为C的两个C-独立点集，且α为α'的加细，则存在C-独立点集'=αai,jδ，满足≥。命题2. 若 =αai,jβ和ψ=α'ai+k,jσ为C的两个C-独立点集，且≥，则存在C-独立点集'=αai,jδ，满足≥。命题3. 若 =αai,jβ和ψ=α'ai,j+kσ为C的两个C-独立点集，且≥，则存在C-独立点集'=αai,jδ，满足≥。由命题1知，在搜寻右下行路的过程中，如果已获得了某一C-独立点集的某一初始截段αai,j和另一C-独立点集ψ的某一初始截段α'ai,j，且有≤，则我们可以停止对ψ的进一步搜寻。由命题2知，在搜寻右下行路的过程中，在某一列j存在某两个C-独立点集的某初始截段=ai1,j1…ais,j和ψ=al1,m1…alt,j，如果≥，但lt>is，则我们可以停止对ψ的进一步搜寻。由命题3知，在搜寻右下行路的过程中，在某一行i存在某两个C-独立点集的某初始截段=ai1,j1…ai,js和ψ=ai1,m1…ai,mt，如果≥，但mt>js，则我们可以停止对ψ的进一步搜寻。由此可见，并不要求搜寻所有C的最大C-独立点集，而可以採用比这简单得多的方法进行计算。那幺按照我们上面的三个命题，来看如下实例：首先我们得到=B（在上的节点用①表示），我们向右下方找路，可以发现，在第4列有两个1，根据命题2，我们选择上面的一个1，也就是说选择第1行的那个1，而不要第2行的那个1。同时我们也发现在第1行也有两个1，由命题3知，我们选择左边的那个1，即第4列的那个1。此时=BO。但是当我们的算法运行到第4行时，=BOOK，由于K在第3行第6列，而本行的1在第1列，在路最后一个节点K的左边，那幺我们必须新建一条路ψ，因为我们并不能确定是否以后就有≥，当算法运行到第6行时，=BOOK，ψ=NEW，=4，=3，我们将S链到路上，此时我们得到最长右下行路=BOOKS，=5。这样我们就可以计算出这两个字元串的匹配程度。
在我们的算法设计过程中，用到了两个技巧。技巧之一，矩阵C不用存储，是动态建立的，节省了空间。技巧之二，本算法并不要求所有的S与T中所有的元素都相互进行比较，也并不存储所有的右下行路，节省了时间和空间。由矩阵中1的出现情况可见，本算法所需的空间和时间都远小于O（mn）

结束语

本文给出了一个与模式匹配不同的，具有若干套用的，串的最大匹配算法，该算法已经在机器上实现，达到了预期的效果。本文仅讨论权值恆为1的情况，对于权值任意的情形不难由此得到推广。