本文的理解建立在此^1以及^2详解之上

本文是对 数据结构–C语言版 书中代码的详解与个人理解

在看到 数据结构–C语言版 里的字符串模式匹配算法时，一开始我不知情Knuth, Morris, Pratt模式匹配是何物，直到有一行代码

    i = failure[i];

真的是百思不得其解，应该说我对于i的作用并不是很明确。此书称此函数为失配函数，对于此数组的作用也算是略知了一二。我这里不赘述算法的基础介绍，着重于理解上可能产生歧义的几个部分。

首先我想先将书上KMP算法的实际匹配算法代码罗列一下。此书是将一段未知字符串先进行失配函数处理，得到failure数组，或者说是网络上说的next数组。

int pmatch(char *string, char *pat)
{
    // 字符串指针 / 模式字符串指针
    int i = 0, j = 0;
    // 命名上稍做了改动 方便理解
    int lengthString = strlens(string), lengthPat = strlens(pat);

    while(i < lengthString && j <lengthPat)
    {
        if(string[i] == pat[j])
        {
            i++;
            j++;
        }
        else if(j == 0)
            i++;
        else
            // 回到可回溯位置(核心)
            j = failure[j - 1] + 1;
    }        

    // 若完成匹配需要让i回归到模式匹配的起始位置
    return (j == lengthPat) ? (i - lengthPat), -1;
}

这里的核心代码确切的说只有一行，就是j = failure[j - 1] + 1。这里j起到的作用就是原文里这一段。

让匹配失败后，不是暴力求解的从pattern的第一位A开始，而是从failure[j-1]+1(在这里failure[j-1]指向的是第一位A，在+1了之后就指向了B)，这一点很重要，很多教程似乎都撇开了next / failure数组和实际求解的关系。

大多将这两者分开介绍，我在仔细联系了两者后发现，其实j = failure[j - 1] + 1这一段的理解是分不开失配函数的求解的。

以下是失配函数

void fail(char *pat)
{
    int n = strlen(pat);
    failure[0] = -1;

    for(int j = 0; j<n; j++)
    {
        // i在此处会被重置，要么为-1要么为上一循环结束值
        i = failure[j - 1];

        while(pat[j] != pat[i+1] && i>0)
            // 核心代码
            i = failure[i];

        if(pat[j] == pat[i+1])
            failure[j] = i+1;
        else
            failure[j] = -1;
    }
}

我想详说一下i的作用，很微妙，似乎不能用一句简单的话概括。还记得刚才匹配失败以后从failure[j-1]+1重新匹配的事实吗。i在这里就是表示，上一个p0,p1…pi = pj-i,pj-i+1…pj出现的位置，也就是前缀在后缀中出现的位置。后边的if/else应该是好理解的。

可以这样代入，某一循环中的某一刻，只要上一循环i>0, 那么pat[i]==pat[j-1]，因此failure[j-1] = i - 1无误(本书中i因为是从-1开始的，算法导论从0开始，本意相同，只有1的差距)。

所以倘若pat[i+1] == pat[j]那么自然failure[j]的值可以直接从上次结果failure[j-1]继承过来failure[j] = i+1了（i会在循环开始被重置为failure[j - 1]，因为我的条件是当前字符相同，所以不进入while），等价于failure[j] = failure[j-1] + 1咯。

核心代码

    i = failure[i];

的理解我花了非常多的时间。

感觉直到目前为止，都没能很透彻的了解。