字符串匹配的形式化定义:假设文本是一个长度为n的数组T[1,2…n],而模式是一个长度为m的数组P[1,2…m],其中m<=n,进一步假设P和T的元素都来自一个有限的字母集Σ的字符，例如Σ={0,1}或者Σ={a,b…z},字符数组P和T通常称为字符串。

如下图所示，如果0<=s<=n-m,并且T[s+1…s+m]=P[1…m],那么称模式P在文本T中出现，并且偏移为s。如果P在T中以偏移s出现，那么称s为有效偏移，否则为无效偏移。字符串匹配问题就是找到有效偏移。（图源《算法导论》）

定理1:假设x，y和z是满足和y⊐z (表示后缀)的字符串，如果|x|<=|y|,那么.（显然，如果x和y都是z的后缀，而且x长度比y小，那么x肯定也是y的后缀）

一、朴素的字符串匹配

朴素字符串匹配即通过一个循环来找到所有的有效偏移，该循环对n-m+1个可能s值进行检查，看是否满足P[1…m]=T[s+1…s+m].

伪代码如下:

在最坏情况下，朴素匹配方式的时间复杂度是O((n-m+1)*m)

朴素匹配尽管代码十分简洁通俗，但一般情况下效率并不高。

 

二、利用有限自动机进行字符串匹配

很多字符串匹配算法都要建立一个有限自动机，它是一个处理信息的简单机器，通过对文本字符串T进行扫描，找出模式P所有出现位置。

一个最简单的有限自动机的图示如下(图源《算法导论》):

字符串自动匹配机

为了详细说明与给定模式P[1…m]对应的字符串匹配自动机，首先定义了一个辅助函数σ，称作对应P的后缀函数。函数σ是一个从∑到{0,1,…m}上的映射，满足σ(x)是x的后缀中属于模式P的最长前缀 的长度。

即            

例如，对于模式P=ab，有σ(ccaca)=1,σ(ccab)=2.

给定模式P[1…m],其相应的字符串匹配自动机定义如下:

·状态集合Q为{0,1…m},开始是0状态，并且只有状态m是唯一接受状态

·对任意的q和a，转移函数δ定义如下

             

考虑两者情况，第一种是a=P[q+1]，使得字符a继续匹配模式，在这种情况下，显然δ(q,a)=q+1.

而第二种情况a≠P[q+1],使得字符a不能继续匹配模式，这时候就需要找到一个更小的字符串，它是P的前缀的同时也是Ti的后缀。因为当创建字符串匹配自动机时，预处理匹配模式和自己，转移函数能很快得到这样的较小的P的前缀。

字符串匹配自动机的伪代码如下:

同时，转移函数的计算过程伪代码如下:

可以这么理解转移函数:即预先计算了在各种匹配长度的情况下，对于待匹配字串Ti中可能出现的任意字符，转移函数都将计算出对应的值。----这样的话，转移函数就如同一张表格一样。就如下图的示例：

显然，当待匹配字串T的字符数目很多时，预先计算转移函数的时间会大幅上升，因为对应的表会扩大。

三、Knuth-Morris-Pratt(KMP)算法

KMP是一种著名的字符串匹配算法，其平均匹配时间为O(n),只用到了辅助函数Π，它在平均时间O(m)内根据模式预先计算出来，并且存储在数组Π[1…m]中。数组Π可以使得我们按需要即时地有效计算出转移函数δ。粗略地说，对任意状态q=0，1…,m和任意字符a∈Σ，Π[q]的值包含了与a无关但在计算δ(q,a)时候需要的信息。

关于模式的前缀函数

模式的前缀函数Π包含模式与其自身的偏移进行匹配的信息。这些信息可以用于在朴素的字符串匹配算法中避免对无用偏移进行检测，也可以避免在字符串匹配的自动机中，对整个转移函数δ的预先计算。

考察一下朴素字符串匹配的过程，如下图所示，在此例中，q=5个字符串已经成功匹配，但模式的第6个字符不能与相应的文本字符匹配。q个字符已经匹配成功的信息确定了相应的文本字符，已知的这q个文本字符使我们能够立刻确定哪些偏移是无效的。在该图例(图源《算法导论》)中，偏移s+1肯定是无效的：

 

假设模式字符P[1…q]与文本字符T[s+1…s+q]匹配，s’是最小的偏移量，s’>s，那么对于某些k<q，满足

       P[1…k]=T[s’+1…s‘+k]

且其中s’+k=s+q

换句话说，已知Pq⊐Ts+q ,我们希望Pq 的真前缀Pk 也是Ts+q 的后缀。我们把P前缀长度范围内的差值q-k加入到偏移s中，用于寻找新的偏移s’,使得s’=s+(q-k);在最好的情况下k=0，因此s’=s+q,能够立刻得出相应偏移量s+1,s+2…s+q-1,在任何情况下，对于新的偏移量s‘，无需把P的前k个字符与T中相应字符进行比较。

下面是预计算过程的形式化说明，已知一个模式P[1…m],模式P的前缀函数是函数Π:{1,2…m}->{0,1…m-1},满足

Π(q)=max{k:k<q且Pk⊐Pq }

即Π[q]是Pq 真后缀字符所对应的在Pq 中的最长前缀长度。如下图所示(图源《算法导论》)：

以下是KMP算法的伪代码流程:

这里，解释COMUPUTE-PREFIX-FUNCTION中的第7行----如果当前模式P字符的下一位和比较字符不匹配，那么只能退而求其次，寻找次长前缀。这个次长前缀一定位于最长前缀中，即所谓次长前缀也就是最长前缀中的最长前缀。

总体而言，KMP的过程就是，不断更新已匹配字串，每次比较模式P和原字串中对应的已匹配部分的下一位！如果不匹配，就更新“已匹配字串”。更新“已匹配字串”的方式是，假设当前已匹配字串长度为q，则利用转移函数Π[q]不断更新，直到产生新的匹配或者q=0为止。

如果q=0，那最为简单，即直接跳过原已匹配字串，直接比较模式P的第一位和当前原串位置i的下一位。

KMP算法有别于有限自动机的特点是，其转移函数实际上并没有将字符a作为参数，仅仅考虑的是“当发生不匹配时”的转移，并且，经过转移后，不一定处于“匹配”状态，而是“可能匹配”的状态，如果还不匹配，则需要继续转移。

也可以这么理解，对于已匹配长度k，即模式P已匹配的前缀部分Pk ，转移函数Π(k)得到的是Pk 中“同时属于Pk 后缀与前缀的最长部分的长度”(比如ababa,同时属于前缀与后缀的最长长度是3，也就是aba)，或者说是“与后缀相同的前缀的最长的长度”。至于为什么是这样呢？这里举例描述一下，比如当前已匹配部分是ababa，下一个字符是x，如果ababax和Pk P[k+1](指的是字段Pk 加上模式P中对应的下一个字符)不匹配，很有可能，Pk (此时为ababa)的某个后缀与x的组合会匹配，比如abax，而这个后缀必须是Pk 的前缀(你可能会说babax难道不行吗？哦不，当然不行，模式P是以a开头的，怎么可能是babax呢，所以能匹配的，必须是模式P的前缀，自然，也会是Pk 的前缀)----那不就是转移函数的定义吗？显然，我们会从有可能的，最长匹配情况开始尝试，也就是Pk 中，与后缀相同的前缀的最长长度。