出自 Farmer_John_LYH

许多时候，我们都需要进行字符串匹配。换句话说，会有人问你，B串是否是A串的子串，A串是否包含B串这样的诡异问题。通常，我们会扳扳手指，从A串的每个位置考虑，最后告诉Ta 是或不是或者我也不会。大多数情况下，只需看头一两个字母，就能发现不匹配。但是，总有一些猥琐的“最坏情况”，例如“A=abababaababacb，B=ababacb”，机械的对比就很恶心了。

这要是一场面试，你将GG在人海之中。瞎扯了这么久，就是为了引出它，KMP。

之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人名的头一个字母。

这个算法，网上的资料数不胜数，但大多数涉及“next(i)”，“跳动”等不明概念，着实令人懵逼。在这里，我选择一种尽量大众化的讲法。

还是令“A=abababaababacb，B=ababacb”,并设A、B串长度分别为n、m，观察一下KMP是如何工作的。可以用两个指针i、j，使A[i−j+1..i]与B[1..j]匹配。 我们通过不断右移i，使j更新，保持关系成立，并令j尽量大。当j=m时，A串包含B串。

图1

我们观察这个样例，当i=j=5时，关系仍成立。但A[i+1]<>B[j+1],故我们需要重新调整j。设新的j为j’，仔细想想，是否满足B[1..j′]=B[j−j′+1..j]呢？先停顿几秒，好好思考，这是否等价于A[i−j′+1..i]与B[1..j′]匹配呢？

一句废话:这个j’越大越好。

等等，如果只需满足B[1..j′]=B[j−j′+1..j]，与A串有什么关系？

也就是说，我们可以对于每个j，预处理一个j’，对吗？

我们设这个j’为Pj,Pj应该是所有满足B[1..Pj]=B[j−Pj+1..j]的最大值。

回到样例，当i=j=5时，已经不满足A[i+1]=B[j+1]，而P5=3(Pi小于i)

故减小j，j=Pj=3，此时A[i+1]=B[j+1]成立，继续更新i，j。

直到i=7，j=5时，又出现了不匹配的情况，j=Pj=3。但此时的j仍不满足A[i+1]=B[j+1]，故再次更新j=Pj=1。

事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1] (如A[8]=d时)。

尽管我们仍可以按照原来的步骤继续更新，但没有人知道P0=?，所以应当直接跳出，继续更新i。而准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。

给出主程序代码

j:=0;    for i:=1 to n do//i的更新    begin            while(j>0)and(b[j+1]<>a[i])do j:=p[j];//不断更新j            if(b[j+1]=a[i])then inc(j);            if(j=m)then //已匹配全串            begin                    writeln('Yes ',i-m+1);                    halt;            end;    end;    writeln('No');

这个代码也可以感性的认识一下：扫描A串，并更新可以匹配到B串的什么位置。

而P数组的初始化有头绪吗？

还用N2甚至N3的时间吗？

实际上，我们可以通过前面已知的P数组，求出当前的。

对于刚才的B=”ababacb”，假如我们已经求出了P[1],P[2],P[3]和P[4]的值，那么P[5]显然等于P[4]+1。为什么呢？由P[4]可以知道，B[1..2]=B[3..4]，现在又有B[3]=B[5]，所以可以直接得到。

P[6]也等于P[5]+1吗？显然不是，因为B[P[5]+1]<>B[6]。那么，我们要考虑“再退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。

p[1]:=0;j:=0;    for i:=2 to m do    begin            while(j>0)and(b[j+1]<>b[i])do j:=p[j];            if(b[j+1]=b[i])then inc(j);            p[i]:=j;    end;

与主程序神似的预处理，其实就是B串与自己先进行了一次匹配。