试想英语文本中第一次匹配模式字符串的需求。

最简单的想法是在文本字符串（下称『文本串』）上按各字符位置暴力匹配模式字符串（下称『模式串』）。

一经完全匹配则直接返回下标，否则返回匹配失败。上述操作即可满足计划。

int brute_match(char *str, char *txt)
{
    int m = strlen(str), n = strlen(txt);
    for (int i = 0; i < n; i++)
    {
        int j = 0;
        for (; j < m && i + j < n; j++)
            if (str[j] != txt[i + j])
                break;
        if (j == m)
            return i;
    }
    return -1;
}

时间复杂度肉眼可见为 $O(nm)$。

且注意到上述做法在特定情况下会极其低效。如 str: "aaaaaaabc", txt: "aaaaaaaaaaabaaaaaaaaaabc"。

基于此，需想方设法优化。

可行的思路是：将匹配过程视为状态跳转过程。只要能到达终态即可确定一次匹配，否则跳到为其计算出的较优状态。

按照这一理念，不妨建一个有穷的 Mealy 状态机。

Mealy 型：次态和现态与输入有关。
Moore 型：次态和现态有关。

这种类型的自动机借助现态和当前提供的输入完成一次跳转，所以在最初结构的设计上至少要用二维数组 nxt[now_state][txt[now]]。

假设已经构建，那么可以很快地写出在状态机上跳转匹配的逻辑。

#define MAX_LEN  100010
/* 假定只有 iso-8859-1 编码范围内的字符表示。*/
int nxt[MAX_LEN][1 << 8];

void state_jmp(char *str, char *txt) {
    int m = strlen(str), n = strlen(txt);
    /* 假定已构建起状态自动机。 */ 
    for(int now = 0, state = 0 /* 初态为 0. */; now < n; now ++)
    {
        /* 由于已完成构建，只需让自动机自行跳转。 */ 
        state = nxt[state][txt[now]];
        if(state == m)
            return now - m + 1;
    }
    return -1;
}

接下来就是构建。设计上：

1. 文本串往往长于模式串，所以自动机中的跳转逻辑应由 模式串完成。
2. 自动机常设初态。此处应选取下标为 $0$ 的字符作为最初的跳转判断从而跳转到第 $1$ 个状态。即 nxt[0/* 此处的含义代表初态 */][str[0/* 此处的含义代表 index 0 */]] = 1;。
   • 于是，模式串得从下标 $1$ 开始取出字符。

一种非常自然的想法就是，假如 和下一个字符能匹配得上，那直接跳到新开的状态上，直到开到终态。否则失配，应全部跳到 最适合当前 的状态。

如何界定 最适合当前 ？

事实上最适合当前的失配状态 最应该是：

在满足先前所有匹配状态的、从零截断到当前字符的模式串子串中，使得 模式串子串的前缀和后缀同时一致且最长 （下称最长双缀）的那个状态。

举例才能有比较深刻的见解。假如使用的模式串是 aaxbaaijkbdcaaxbaax。

再假设有个首部和模式串很相似的文本串 aaxbaaijkbdcaaxbaa[?]... 要与其匹配。同时，需要说明的是整个过程要用到两个指针。

一个在文本串上，不会回跳，顺序挑取文本串上的字符，与另一个在模式串上可能会回跳以优化匹配过程的指针所指向的字符比较，从而决定模式串上的指针下一步是往前走还是往后跳。

光是这么表述可能还是比较抽象，但是不急，后面有具体例子。

假如已经匹配到了 aaxbaaijkbdcaaxbaa，现在只看最后的 [?] ，就有如下处理策略。

• 如果 [?] 失配成字符 a，那么失配相当于匹配到了前缀 aa；所以直接将已经匹配到 aaxbaaijkbdcaaxbaa 为止，模式串上的指针拨回下标 $1$；
• 如果 [?] 失配成字符 i，那么失配相当于匹配到了前缀 aaxbaai，模式串上的指针相应拨回 $6$；
• 如果 [?] 匹配为 x 则完成一次匹配。
• 否则陷入了最劣的失配情况，直接让指针归零，以回到初态重新匹配。

感性的理解就是如此。

再来考虑从头到尾如何构建整个状态自动机。

因字符随意的性质，便要求当前状态在没有得到输入前，直接向当前失配的状态跳转，否则按照模式串提供的输入，跳转到下一个状态。失配状态需要在构建过程中更新以确保后继的正确性。

那么，上述通过状态自动机完成匹配的实现如下。

#define MAX_LEN  100010
int nxt[MAX_LEN][1 << 8];

void state_jmp(char *str, char *txt) {
    int m = strlen(str), n = strlen(txt);

    nxt[0][str[0]] = 1;

    // 模式串的自我匹配用于构建跳转状态自动机。
    for(int now = 1, fail_state = 0; now < m; now ++) {
        for(int c = 0; c < 0x100; c ++)
            nxt[now][c] = nxt[fail_state][c];   // 没输入前，所有次态失配到当前的失败状态。

        nxt[now][str[now]] = now + 1;           // 匹配成功，重整正确的次态

        fail_state = nxt[fail_state][str[now]]; // 当前的失败状态随字符更新到下一失败状态
    }

    for(int now = 0, state = 0; now < n; now ++)
    {
        state = nxt[state][txt[now]];
        if(state == m)
            return now - m + 1;
    }
    return -1;
}

时间复杂度肉眼可见为 $O(n + 256m)$。

所以，程序此时的瓶颈在于 nxt 数组的优化。还以模式串 aaxbaaijkbdcaaxbaax 为例，受前后缀一致且最长启发，此时考察自己与自己匹配而生成 nxt 数组时如何移动。

$$\begin{aligned} \operatorname{str}: &[\texttt{aaxbaa|ijkbdc|aa xb aa|x}] \\ % \operatorname{str}: & \texttt{aaxbaa|ijkbdc|aa xb aa|x} &&(\text{mismatch}_1)\\ \operatorname{str}: &\texttt{\ aa|xb|aa|ijkbdcaaxbaax} &&(\text{mismatch})\\ \operatorname{str}: &\texttt{\ aa|xbaaijkbdcaaxbaax} &&(\text{match}) \end{aligned}$$

注意到如每次为各个下标记录截止于下标之前（不包含下标所指字符串本身）最长双缀的长度，那么在逻辑上形成以下的构造。

# 记 n[i] := nxt[i] 作为 str[0:i) 的最长双缀长度。
# 下图的 L 段和 R 段是标视出来的最长双缀。
#                                           i
#         0                                /
# str:    |_________|__________|_________|?.........
# str:    |_________|?_________|_________|*.........    # 此行作为自己与自己匹配的模式串。
#              L    ||              R     
#                  /  \
#            n[i]-1  n[i]
#               |      |
#       test_fail-1   test_fail 首次判断时在 test_fail 处比较 str[test_fail] == str[i] 是否成立

每轮匹配通过比较 str[i] 和 str[nxt[i]]（也即 str[test_fail] ） 来更新 nxt 数组。

• 如果一致，只需让 nxt[i + 1] = test_fail + 1 即可。
• 否则继续取 str[0:nxt[i])，即 str[0:test_fail) 内的 nxt[nxt[i]] 去比较，直到相等或者失配到 nxt[nxt[...]] 为空还依然匹配不上为止。

那么，最后得到短而精悍的模板。

int kmp(char *str, char *txt)
{
    int m = strlen(str), n = strlen(txt);
    // nxt[0] = 0; 可以不用写，一般用不着。
    for (int i = 1, test_fail = nxt[1]/* 单个字符的双缀只有空，是本身则没意义。 */; i < m; i++)
    {
        while (test_fail && str[i] != str[test_fail]) 
            test_fail = nxt[test_fail];
        test_fail += str[i] == str[test_fail];
        nxt[i + 1] = test_fail;
    }

    for (int i = 0, test_fail = nxt[0]; i < n; i++)
    {
        while (test_fail && str[test_fail] != txt[i]) test_fail = nxt[test_fail];
        test_fail += txt[i] == str[test_fail];

        if (test_fail == m) return i - m + 1;
    }
    return ~0;
}

后记

需要指出，此处用的 nxt 数组含义是使得失败后选取到最优位置的公共双缀，并作为模式串上的下标与文本串中的特定位置不断地比较、跳转、比较直至满足循环跳出条件。

这绝非应试定义的 $\texttt{nextval}(i) = \begin{cases}\texttt{nextval}(j) & \texttt{str}(i)=\texttt{str}(j)\\\texttt{next}(i)&\texttt{str}(i)\neq\texttt{str}(j)\end{cases}$。或者

$$\texttt{next}_i = \begin{cases} 0 & i = 0 \\ j &\texttt{pat}[0:j) = \texttt{pat}[i-j:i) \\ \boxed{1} & \text{others} \\ \end{cases}$$

如果考到 next，记住公式给出的定义；
如果是 nextval，同样要记住公式定义。

注意匹配过程的清晰，以防误判而答错题。