数据结构历年考研真题对应知识点（串的模式匹配）

4.2串的模式匹配

4.2.2串的模式匹配算法——KMP算法

【KMP 匹配过程中指针变化的分析(2015)】

【KMP 匹配过程中比较次数的分析(2019)】

4.2串的模式匹配

4.2.2串的模式匹配算法——KMP算法

【KMP 匹配过程中指针变化的分析(2015)】

最终得到子串指针变化公式 j=next[ j ]。在实际匹配过程中，子串在内存中是不会移动的，而是指针发生变化，画图举例只是为了让问题描述得更形象。next[ j ]的含义是:当子串的第 j 个字符与主串发生失配时，跳到子串的 next[ j ]位置重新与主串当前位置进行比较。

如何推理 next 数组的一般公式?设主串为' $s_{1}s_{2}...s_{n}$ '，模式串为 $'p_{1}p_{2}...p_{m}'$ ，当主串中第 i 个字符与模式串中第 j 个字符失配时,子串应向右滑动多远,然后与模式中的哪个字符比较?

假设此时应与模式串的第k(k<j)个字符继续比较，则模式串中前 k-1 个字符的子串必须满足下列条件，且不可能存在 k'>k 满足下列条件:

$p_{1}p_{2}...p_{k-1}=p_{j-k+1}p_{j-k+2}...p_{j-1}$

若存在满足如上条件的子串，则发生失配时，仅需将模式串向右滑动至模式串的第k个字符和主串的第i个字符对齐，此时模式串中的前k-1 个字符的子串必定与主串中第i个字符之前长度为 k-1 的子串相等，由此，只需从模式串的第k个字符与主串的第i个字符继续比较即可,如图 4.5 所示。

当模式串已匹配相等序列中不存在满足上述条件的子串时(可视为 k=1)，显然应该将模式串右移 j-1 位，让主串的第 i 个字符和模式串的第1个字符进行比较，此时右移位数最大。

当模式串的第1个字符(j=1)与主串的第i个字符发生失配时，规定 next[1]=0（可理解为将主串的第i个字符和模式串的第1个字符的前面空位置对齐，即模式串右移一位。）将模式串右移一位，从主串的下一个位置(i+1)和模式串的第1个字符继续比较。

通过上述分析可以得出 next 函数的公式:

上述公式不难理解，实际做题求 next 值时，用之前的方法也很好求，但要想用代码来实现，貌似难度还真不小，我们来尝试推理求解的科学步骤。
首先由公式可知

next[1]=0

设 next[j]=k，此时k应满足的条件在上文中已描述。
此时 next[ j+1 ]=?可能有两种情况:
(1)若 $p_{k}=p_{j}$ ，则表明在模式串中

$p_{1}...p_{k-1}p_{k}=p_{j-k+1}...p_{j-1}p_{j}$

并且不可能存在 k'>k 满足上述条件，此时 next[ j+1 ]=k+1，即 next[ j+1 ] = next[ j ]+1

(2)若 $p_{k}\neq p_{j}$ ，则表明在模式串中

$p_{1}...p_{k-1}p_{k}\neq p_{j-k+1}...p_{j-1}p_{j}$

此时可将求 next 函数值的问题视为一个模式匹配的问题。用前缀 $p_{1}...p_{k}$ 去与后缀 $p_{j-k+1}...p_{j}$ 匹配，当 $p_{k}\neq p_{j}$ 时，应将 $p_{1}...p_{k}$ 向右滑动至以第 next [k]个字符与 $p_{j}$ 比较，若 $p_{next[k]}$ 与 $p_{j}$ 仍不匹配,则需要寻找长度更短的相等前后缀,下一步继续用 $p_{next[next[k]]}$ 与 $p_{j}$ 比较,以此类推,直到找到某个更小的 k'=next[next… [k]](1<k'<k<j)，满足条件

$p_{1}...p_{k}=p_{j-k'+1}...p_{j}$

则 next [ j+1 ]=k'+1

也可能不存在任何 k'满足上述条件,即不存在长度更短的相等前缀后缀,令 next[ j+1 ]=1

理解起来有一点费劲?下面举一个简单的例子。

图 4.6的模式串中已求得6个字符的next值,现求 next [7],因为next[ 6 ]=3,又 $p_{6}\neq p_{3}$ 则需比较 $p_{6}$ 和 $p_{1 }$ (因next[ 3 ]=1),由于 $p_{6}\neq p_{1}$ ,,而next[1]=0,因此

next [7]=1；求next [8]，因 $p_{7}=p_{1}$ ,则next [8]=next [7]+1=2;求next [9]，因 $p_{8}=p_{2}$ ,则 next [9]=3。

通过上述分析写出求 next 值的程序如下:

void get_next(SString T,int next[]){
    int i=1，j=0;
    next[1]=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i; ++j;
            next[i]=j;    //若pi=pj，则 next[j+1]=next[j]+1
        }
        else
            j=next[j];    //否则令j=next[j]，循环继续
    }
}

计算机执行起来效率很高，但对于我们手工计算来说会很难。因此，当我们需要手工计算时还是用最初的方法。

与 next 数组的求解相比,KMP 的匹配算法相对要简单很多，它在形式上与简单的模式匹配算法很相似。不同之处仅在于当匹配过程产生失配时，指针i不变，指针 j退回到 next[j]的位置并重新进行比较，并且当指针j为0时，指针i和j同时加 1。即若主串的第i个位置和模式串的第1个字符不等，则应从主串的第 i+1个位置开始匹配。具体代码如下:

int Index_KMP(SString S,SString T,int next[]){
    int i=1，j=1;
    while(i<=S.length && j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){
            ++i; ++j;         //继续比较后继字符
        }
        else
            j=next[j];        //模式串向右移动
    }
    if(j>T.length)
        return i-T.length;    //匹配成功
    else
        return 0;
}