状态机和KMP算法

前言

字符串的匹配是编写程序的时候经常遇到的一个问题，也是计算机处理的基础问题之一。最简单的方法是循环字符串，一位一位地进行匹配，也可以使用正则表达式。今天本文讨论用状态机的模型如何理解和解决字符串匹配的问题。

状态机 FSM

状态机全称有限状态机（英语： finite-state machine ，缩写： FSM ）又称有限状态自动机（英语： finite-state automation ，缩写： FSA ），简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。我个人的理解是我们的某一类型的问题在解决过程中能够抽象出有限个不同的状态，不同的问题只是问题解决过程中状态的转移过程不同，当我们将状态和状态之间的关系抽象出来，那么这一类问题我们全部能用一套逻辑来解决。每一个状态机应该能够接受相同的输出，每一个状态机都应该知道自己的下一个状态是什么（输出只依赖于当前状态，和输入无关的称为 moore 机，输出依赖于输出和当前状态的称为 mealy 机）。用 JavaScript 模拟状态机的模型大概如下面的形式。

function fsm_start(input) {
    //当前状态机的逻辑
    return next_fsm;//返回下一个状态函数
}

let state = fsm_start//设置初始状态

while (condition) {
    state = state(input)//执行当前状态机函数，并将
}

状态机的字符串匹配

其实我们在编程的过程中其实一直和状态打交道，比如 if/else ， switch/case 等，有时候当我们面对一些比较复杂的问题的时候如果能够用有限状态机来描述，那么问题的逻辑可能更清晰。代码结构的可读性也更强。

比如字符串的匹配问题，当我们想要知道某个字符串中是否包含另一个字符串时，状态机就能够帮我们解决问题。比如我们要寻找一个字符串中是否有 abcdef 这串字符，如果使用状态机模型，我们可以这样实现：

function match(string) {
    let foundA = foundB = foundC = foundD = foundE = false;
    for (let c of string) {
        if (c === 'a') {
            foundA = true;
        } else if (foundA && c === 'b') {
            foundB = true;
        } else if (foundB && c === 'c') {
            foundC = true;
        } else if (foundC && c === 'd') {
            foundD = true;
        } else if (foundD && c === 'e') {
            foundE = true;
        } else if (foundE && c === 'f') {
            return true
        } 
    }
    return false;
}

console.log(match('abcdeabcdef'))//true

但是如果我们想要匹配的字符串时 abcabx 这种有重复部分的时候我们就没法用上面那种方法了，因为当我们匹配到 x 这一位的时候有可能是 c 我们需要回到检测到 c 的状态，这种情况用上面的方法就没法实现，因为 if/else 结构是没法跳转到某一步的。在不用状态机的情况下我们可以用下面的“暴力”方法实现，用 i 和 j 分别表示字符串和 pattern 当前正在匹配的字符的下标，匹配成功则都 +1 ，否则 i = i - j +1 ， j = 0 。循环继续的条件是字符串还没匹配完，并且也没有成功匹配出 pattern 。大概过程如下图。

function match(string, pattern) {
    let i = j = 0;
    for (; i < string.length && j < pattern.length; i++) {
        if (string[i] === pattern[j]) {
            j++;
        } else {
            i -= j;
            j = 0;
        }
    }
    if (j === pattern.length) {
        let s_index = i - pattern.length;
        return [s_index, string.slice(s_index, s_index + pattern.length)];
    } else {
        return 'failed'
    }
}

console.log(...match('abababababcabcabxababab', 'abcabx'))

用上面的方式我们可以堆任意 pattern 进行字符串的匹配。但有个问题是当匹配失败的时候我们是将 i 前进一位，然后对 pattern 从头进行匹配，对一些有重复部分的 pattern 显然是没有效率的。比如 abcabx ，当我们匹配到 abcabc 的时候我们没必要从 bcabc 从头匹配，只需匹配第二个 abc 后面是不是 abx 就可以了。而如果使用状态机模型，则可以利用状态的跳转来实现这样的目的。

function match(string) {
    let state = start;
    for (let c of string) {
        state = state(c);
    }
    return state === end;
}

function start(c) {
    if (c === 'a') {
        return foundA;
    } else {
        return start;
    }
}

function foundA(c) {
    if (c === 'b') {
        return foundB;
    } else {
        return start(c);
    }
}

function foundB(c) {
    if (c === 'c') {
        return foundC;
    } else {
        return start(c);
    }
}

function foundC(c) {
    if (c === 'a') {
        return foundA2;
    } else {
        return start(c);
    }
}

function foundA2(c) {
    if (c === 'b') {
        return foundB2;
    } else {
        return start(c);
    }
}

function foundB2(c) {
    if (c === 'x') {
        return end;
    } else {
        return foundB(c);//跳转到找到第一个b的状态
    }
}

function end() {
    return end;
}

console.log(match('ababaabcabcabxab'))//true

用状态机模型的方式实现，代码解构也很清晰，每一个状态直接是没有关系的，我们可以通过控制状态的跳转来控制流程，提高匹配的效率。但是这样的实现方式显然也不好，每次出现一个新的 pattern 我们都要重新写代码，并没有将状态机的逻辑完全抽象出来。

KMP 算法

KMP 算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式字符串本身。—— 《算法4》

在匹配字符串这个问题上，最重要的就是当一个字符匹配失败的时候，我们怎么进行下面的匹配才是最高效的。比如上面的非状态机的实现方法，当我们匹配失败的时候，我们已经匹配成功了 [0, j - 1] 位了，此时我们将 i 回退到未匹配状态并右移一位再从 j = 0 开始匹配，这显然是非常低效的。比如 abcabx 这样的 pattern ，当我们在 x 这一位匹配失败的时候，我们并不一定需要全部重新匹配，因为如果我们当前这一位是 c 的话我们可以优化我们的匹配过程，如下图。

如果我们能找到 pattern 的规律就能够很好地优化我们的过程， kmp 算法正是一个很好字符串匹配的算法。 kmp 算法有两种实现方式，一种是基于确定有限状态机的 DFM(deterministic finite-state automaton) ，另一种是基于部分匹配表 PMT(Partial Match Table) 的实现。我个人觉得 PMT 的思路更容易理解一点，但是 DFM 则是一种更高级的方式，抽象的更彻底，直接揭示了子串匹配的本质。

DFM

在谷歌上搜索 DFM 的中文结果很少，大部分的 KMP 算法的文章都是讲解 PMT 中的 next 数组的含义，通过状态机来讲解这个算法的非常少，而且质量也不是很高，要么一带而过要么太过冗长而讲不清楚。大部分的 DFM 文章都来源于 《算法》第四版 中的 5.3 章节 Substring Search 中的 Knuth-Morris-Pratt substring search ，以及作者 Robert Sedgewick 对该算法的讲解视频（视频地址贴在 这里 ）。我最后也是直接看原文和视频来理解的（虽然英文很烂，硬着头皮看，不过视频还好，没有什么听力难点， 学好英语 对 程序员 太重要了），这里整理一下我的理解，我认为整个思路其实非常简单和清晰，我认为其中思维的一个难点（其实是我们思维的一个惯性）就是我们要把 pattern 和要匹配的字符串分开思考。

首先贴上《算法》中的对字符串 ABABAC 作为 pattern 的状态机图示。

对这两个图做一个简单的解释，上方的是一个矩阵，下方是一个图表，他们表达的是同一个有限状态机，只是形式不同。这两张图表达的就是 ABABAC 进行匹配的状态机。所有的数字表示的都是状态，而这个状态数字可以理解成当前已经成功匹配了几个字符，比如状态 4 表示已经成功匹配到了 ABAB 才进入状态 4 。下方图表的箭头则表示状态的转移，注意每个箭头上都有一个字母，表示这个转移是因为这个字母的输入。以状态 3 为例，我们此时已经成功匹配到了 ABA 三个字符，下面我们接受的输入有三种可能 A B C ，当接收 B 时，我们成功匹配进入状态 4 ，当接收 A 时，我们回到了状态 1 ，当我们接收 C 时回到状态 0 。我们的状态机接收两个参数，一个是当前状态，一个是输入，得到的结果就是应该转移的状态。在矩阵图中， j 是当前所处的状态， pat.charAt(j) 表示 pattern 在当前要匹配的字符，纵向的 dfa[][j] 则表示输入，中间的矩阵表示要转移到的状态，比如矩阵中位置 [0,0] 的 1 表示，在状态 0 接收输入 A ，状态转移到 1 。

这里需要注意，我们的状态机只和 pattern 有关，就是不管我们要进行匹配的字符串是什么，只要我们的 pattern 不变，状态机就不变，举个例子就是不管待匹配的字符串是 ababababaaacaba 还是 abafabafagaba ，只要 pattern 是 ABABAC ，状态机就不变，所以在分析状态机的时候我们只需要分析在 pattern 中出现的字符。

我们将待匹配的字符串叫做 string，把要匹配的子串成为 pattern

这里的状态是我们自己分析的，但是要写成程序我们必须抽象出一个所有 pattern 的状态机规律。我们想一想我们是如何得到状态转移 ( state transition ) 的结果的。以状态 5 为例，当我们在状态 5 匹配失败 ( mismatch ) 的时候，我们如何确定我们要转移到哪个状态呢。当我们在状态 5 匹配失败的时候，代表我们已经成功匹配 ABABA 五个字符，而我们要获得转移状态，只要将已经匹配的五个字符串的首位去掉，剩下的 BABA 再进入状态机进行匹配，得到的状态就是我们要转移的状态。这里可能不是很好理解，我用下面的图来解释。

上图中共有三个部分，第一部分使我们在状态 5 匹配失败，第二部分是我们用“暴力”方法时的图示，第三种是我们用状态机的方法实现的图示。我们可以看出 kmp 算法的精妙之处就是当我们匹配失败时，不是像暴力解法一样完全放弃我们这次匹配从头开始，而是将匹配过程中得到的有用的信息作为下一次匹配的基础。当我们在状态 5 匹配失败时， ABABA 这个串在当前位置肯定是走不通了，但是在我们可以试试看状态 0，1，2，3，4 中有没有在当前位置能用得上的，如果有我们就可以直接使用，这让我们虽然当前位置匹配失败，但做的不是无用功，而是把有用的信息保存下来。我们的状态代表的是我们当前匹配成功几个字符，既然状态 5 失败了，那么我们试试状态 4 也就是 BABA ，也失败；再试试状态 3 也就是 ABA ，成功了。我们尝试状态的过程，也就是将 pattern 不断右移的过程，在这个过程中我们不需要移动上方 string 的指针。

状态转移的本质就是将我们匹配成功的信息保存起来，在下次匹配时拿出来直接用。比如我们要达到状态 5 ，我们必然要经过 0，1，2，3，4，5 而不可能直接到状态 5 ，所以当我们在状态 5 失败了，我们完全可以看看是不是可以从别的状态直接开始。就像我们有时候修改代码中的 bug ，我们一般不会把我们的代码全部推倒重写，而是定位问题发生点，然后不断将问题向上追溯，直到追溯到一个我们觉得可用的状态，就接着这个可用的状态接着写。

我们搞清楚了状态转移的原理，剩下的一个最重要的问题就是我们如何抽象出状态转移的通用规律，即拿到一个未知 pattern 我们也能知道每一个状态下如何转移。我们把状态的转移分成两种情况，一种是匹配成功，一种是匹配失败。如果匹配成功，非常简单，直接进入下一个状态；如果匹配失败，我们会向前进行状态转移。那么状态转移的规律是什么呢？我们还是以上面的 ABABAC 为例子，我们已经通过自己的分析得到了，当我们在状态 5 的时候匹配失败，会回到状态 3 并刚刚匹配失败的输入作为状态 3 的输入，也就是说在状态 5 和状态 3 输入 A 和 B 的结果是相同的，我们在计算状态 5 的状态转移时，输入 C 直接进入下一状态，而输入 A 和 B 的结果可以直接调用状态 3 的结果。

剩下的一个问题是最关键的，我们如何确定当前所在状态 j 的匹配失败的状态转移。我们用一个变量 X 表示当前状态下匹配失败要跳转到的状态。我们上面说过，当状态 5 匹配失败时，我们实际上是将 ABABA 去掉首位编程 BABA 进入状态机运算得到的结果作为状态 5 的 X ，也就是说当我们在状态 j 匹配失败时，我们是将 pattern 中已经匹配成功的 pattern[0] - pattern[j - 1] ,去掉首位，也就是 pattern[1] - pattern[j - 1] 放入状态机中运算，得到的结果作为 X 。我们还是以 ABABAC 为例，分析一下各个状态的 X 。

1. 状态 0 ，目标字符 A ，一个字符都没有匹配成功，不考虑。
2. 状态 1 ，目标字符 B ，匹配成功 A 去掉首位为 "" ，放入状态机中运算结果为 0 ， X 为 0 。
3. 状态 2 ，目标字符 A ，匹配成功 AB 去掉首位为 B ，放入状态机中运算结果为 0 ， X 为 0 。
4. 状态 3 ，目标字符 B ，匹配成功 ABA 去掉首位为 BA , 放入状态机中运算结果为 1 , X 为 1 。
5. 状态 4 ，目标字符 A ，匹配成功 ABAB 去掉首位为 BAB ，放入状态机中运算结果为 2 ， X 为 2 。
6. 状态 5 ，目标字符 C ，匹配成功 ABABA 去掉首位为 BABA ，放入状态机中运算结果为 3 ， X 为 3 。

我观察一下可以发现，去掉没意义的状态 0 ，剩下的五个状态，求 X 所用的字符串分别是 "" ， B ， BA ， BAB , BABA ，而目标字符分别是 B ， A ， B ， A ， C ，状态 2 的 X 值就是状态 1 的 X 对应状态输入状态 2 的目标字符得到的状态。

可能有点绕，不是很好表述，状态 5 的 X 就是 BABA 在状态机中的运算结果，状态 4 的 X 就是 BAB 在状态机中的运算结果， BABA 的运算结果就是 BAB 的运算结果再输入一个 A ，而这个 A 就是状态 4 的目标字符。也就是说我们知道状态 4 的 X 就已经能求得状态 5 的 X ，以此类推我们从状态 1 就能求到之后所有状态的 X ，而状态 1 的 X 为 0 。

《算法》第四版中有两张图可以来辅助理解。

对 DFM 的总结：

1. 每个状态都有其对应的 X ，当该状态下匹配失败时，则转移到 X 状态。

2. 将 j 状态的不匹配输入，输入到其对应的 X 状态，结果是相同的。（ X 必然小于 j ）

2. j - 1 状态 X 值对应的状态输入 j - 1 状态的目标字符得到的结果状态和 j 状态的 X 值对应的状态是相同的，即 j 状态对应的 X 可由 j - 1 状态计算得到。

下面就是具体代码，我们可以分成两个部分，一个部分是检索子字符串，另一部分是管理状态机。第一部分的代码非常简单，循环字符串，将字符交给状态机，当字符循环完毕没匹配成功则返回 false ，若匹配成功则返回 success 。第二部分则是生成对应 pattern 的状态机。

function match(s, p) {
    let M = p.length,
        N = s.length,
        i = 0,
        j = 0,
        dfa = KMP(p);

    for (; i < N && j < M; i++) j = dfa[j][s.charCodeAt(i)];
    if (j === M) return 'match success at index of ' + (i - M);
    return 'false';
}

function KMP(p) {
    let X = 0,
        R = 256,
        M = p.length,
        dfa = new Array(M);
    for (let i = 0; i < dfa.length; i++) dfa[i] = new Array(R); //创建长度为dfa.length的数组，每一项为一个对象

    //初始化dfa[0],即初始的X状态，后面的状态要用这一状态来复制
    for (let i = 0; i < R; i++) dfa[0][i] = 0;
    dfa[0][p.charCodeAt(0)] = 1; //状态0时匹配到第一位总是进入状态1

    //生成后面的状态机
    for (let j = 1; j < M; j++) {
        for (let c = 0; c < R; c++) dfa[j][c] = dfa[X][c]   //设置状态j的匹配失败项，从状态X复制
        dfa[j][p.charCodeAt(j)] = j + 1;//设置匹配成功项
        X = dfa[X][p.charCodeAt(j)] //计算下一阶段的 X
    }
    return dfa;
}

console.log(match('asdfasdfsafabababafabababacasdf', 'ababac'));

这里的代码使用 javascript 写的，所以 KMP 中我们需要手动初始化状态 0 （也就是默认的 X ）的状态跳转。《算法》中的代码使 Java ，所以整形数组的项的默认值是 0 ，不需要处理。 javascript 中， new Array() 方法创建的固定长度的数组其实只是一个确定了 length 属性的数组对象，里面并没有任何元素（不要理解成都是 undefined ）。

还有一点就是算法中是用 charAt ，也就是 javascript 中的 charCodeAt 方法来设置状态机的输入，每个状态对应 256 种输入，也就是扩展 ASCII 码的全部字符数，这样做的好处是我们完全不需要考虑 match 函数中的输入字符（只要在扩展 ASCII 范围内）。不过这样创建的二维数组特别大，我认为可以先对 pattern 进行一个处理，取出 pattern 中所有的不重复的字符放入对象，只要匹配的字符不在这个对象中，直接将 j 设置为 0 。具体代码如下。

function match(s, p) {
    let M = p.length,
        N = s.length,
        i = 0,
        j = 0,
        o = {},
        dfa = KMP(p);

    //生成pattern中不重复元素的对象
    for (let t of p) {
        if (!o[t]) o[t] = t; 
    }

    for (; i < N && j < M; i++) {
        j = !!o[s[i]] ? dfa[j][s[i]] : 0;
    }
    if (j === M) return 'match success at index of ' + (i - M);
    return 'false';
}

function KMP(p) {
    let X = 0,
        R = 256,
        M = p.length,
        o = {},
        dfa = new Array(M);

    //生成pattern中不重复元素的对象
    for (let t of p) {
        if (!o[t]) o[t] = t; 
    }

    for (let i = 0; i < dfa.length; i++) dfa[i] = {...o}; //创建长度为dfa.length的数组，每一项为一个对象

    //初始化dfa[0],即初始的X状态，后面的状态要用这一状态来复制
    for (let key in dfa[0]) {
        dfa[0][key] = 0;
    }
    dfa[0][p[0]] = 1; //状态0时匹配到第一位总是进入状态1

    //生成后面的状态机
    for (let j = 1; j < M; j++) {
        for (let c in o) dfa[j][c] = dfa[X][c]  //设置状态j的匹配失败项，从状态X复制
        dfa[j][p[j]] = j + 1;//设置匹配成功项
        X = dfa[X][p[j]] //计算下一阶段的 X
    }
    console.log(dfa)
    return dfa;
}

console.log(match('asdfasdfsafabababafabababacasdf', 'ababac'));

//[
//  { a: 1, b: 0, c: 0 },
//  { a: 1, b: 2, c: 0 },
//  { a: 3, b: 0, c: 0 },
//  { a: 1, b: 4, c: 0 },
//  { a: 5, b: 0, c: 0 },
//  { a: 1, b: 4, c: 6 }
//]
//match success at index of 21

状态机的运用让我们在搜索的效率上得到了很大的提高，但是我们需要额外维护一个状态机，也是用空间换时间。暴力解法的时间复杂度最坏情况是 O(m*n) ， DFM 的解法的时间复杂度则为 O(n) .

PTM 部分匹配表

在搜索引擎上能找到的关于 KMP 算法的文章大部分都是 PTM 实现的，所以我也是最先看的 PTM 实现。相对于 DFM 的实现， PTM 的实现可能更直白一点，没有那么巧妙。而且我感觉 PTM 的思维也影响到了我对 DFM 的理解。

PMT 叫做部分匹配表，其实就是把 DFM 中找到的 X 的值进行手动计算。在 DFM 中我们对 X 的理解是一个在匹配失败的时候跳转的状态，在 PTM 中对这个值的理解就是当前状态下的最长前后缀。

我们先来介绍前后缀的概念。对于一个字符串，包含该字符串的首位且不包含末位的子串就是这个字符串的前缀，而包含该字符串的末位且不包含首位的子串就是这个字符串的后缀。比如对于字符串 ababa ，他的前缀包括 a ab aba abab ， 他的后缀包括 a ba aba abab 。我们在 DFM 中找的 X 在 PTM 的理解中就是寻找最长的相同前后缀。比如 ababa 的最长相同前后缀就是 aba ，长度为 3 。我们在 DFM 中的 ABABAC 的 j 为 5 的情况下对应的 X 就是 3 。这个原理其实也很简单，看下图。

在 DFM 中我们理解这张图是我们在 j 为 5 的状态匹配失败，此时我们将前面匹配成功的五位 ABABA 去掉首位再放到状态机中计算得到的输出作为 X 。在 PTM 中其实就没有所谓的状态了，我们在当前这一位匹配失败了，就找出前面匹配成功的字符串 ABABA 中的最长前后缀，也就是 ABA 。其实我们仔细思考一下，这两种方法其实并没有本质的区别，把 BABA 放到状态机中计算就是找最长前后缀，只不过 DFM 更巧妙一些，我们不需要真的去找最长的前后缀。可以说 DFM 的做法是着眼于各个状态的关系，用这个关系来解决问题；而 PTM 则更简单直接一点，我这个状态的问题就利用这个状态自己解决。

所以在 PTM 中我们可以得出 pattern 的各位对应的最长相同前后缀的长度，这个长度所形成的表就叫做部分匹配表。我们用两个 pattern 来看一下对应的 PTM 。第一个是 ababac ，第二个是 abababca 。

如何求这个 PTM 呢？其实 PTM 就是 pattern 自己和自己匹配然后得出的结果，因为我们在用 pattern 和字符串匹配的时候，匹配成功的组合必然就在 pattern 中，匹配失败的时候我们需要移动的也只是 pattern 的指针，所以 PTM 只和 pattern 相关。大概的逻辑是：从 pattern[1] 开始不断用 pattern 进行匹配，用两个指针分别指向两个 pattern 当前的位置（如下图），用一个数组 arr 储存 i 指针对应位的最长前后缀的长度。匹配成功则两个指针都右移， arr[i] = j ；失败则 i 不动， j 赋值为 arr[j-1] 的值；如果 j 为 0 ，则 arr[i] = 0 并且 i 向右移动一位。整个过程就是 DFM 中的某一位匹配失败时，用前面匹配成功的部分去掉第一位放进状态机匹配的详细过程。

function PMT(p) {
    let i = 1,//i和j错开
        j = 0,
        arr = [0];//第一位的最长前后缀为0

    while (i < p.length) {
        if (p[i] === p[j]) {
            j++;
            arr[i] = j;
            i++;
        } else if (j === 0){
            arr[i] = 0;
            i++;
        } else {
            j = arr[j - 1];//匹配失败的时候，j回到j-1位的最长前后缀的位置
        }
    }
    return arr;
}
console.log(PMT('ababac'))
console.log(PMT('abababca'))
//[ 0, 0, 1, 2, 3, 0 ]
//[ 0, 0, 1, 2, 3, 4, 0, 1 ]

我们上面求得的这个 PTM 在实际编码中并不方便，我们上面的 i 指针实际上相当于我们在 i + 1 位匹配失败，求得前 1 - i 位的最长相同前后缀（即 DFM 中的把 1 - i 位放到状态机中执行），所以 i 位的 PTM 值其实是给 I + 1 位用的，基于这个原因，我们将 PTM 表向右移动一位，最左边补上一个 -1 （单纯是为了编程方便），最右边的位舍去，得到如下的 next 表。

我们也可以直接求出 next 数组，代码如下。

function PTM2(p) {
    let arr = [-1];
    let i = 0, j = -1;

    while (i < p.length)
    {
        if (j == -1 || p[i] == p[j])
        {
            ++i;
            ++j;
            arr[i] = j;
        }
        else
            j = arr[j];
    }
    //arr.pop();
    return arr;
}
console.log(PTM2('ababac'))
console.log(PTM2('abababca'))
//[ -1, 0, 0, 1, 2, 3, 0 ]
//[ -1, 0, 0, 1, 2, 3, 4, 0, 1 ]

我们可以看出我们设置 arr[0] 和 j 为 -1 的情况下，我们可以将 j 回到第一位和匹配成功两个状况合并，因为 j 回到第一位理论上只要移动 i ，但当我们设置 j 为 -1 的时候，我们也需要 j++ ，这就和匹配成功的逻辑相同了，让我们的代码更简单更清晰。得到 next 数组之后剩下的就是写 match 函数，逻辑和 next 数组的逻辑基本相同。

function match(s, p) {
    let i = 0,
        j = 0,
        arr = PMT(p);

    while (i < s.length) {
        if (j === -1 || s[i] === p[j]) {
            if (j === arr.length - 1) return 'success';
            i++;
            j++;
        } else {
            j = arr[j];
        }
    }
    return 'failed';
}

总结

我个人认为动态规划是有限状态机的一种特殊形态。 DFM 的实现花了很长时间才领会，主要就是因 PTM 的想法有点先入为主的理解，他们的本质是一样的，但是 DFM 把那张部分匹配表隐藏在算法中了，我们不再关心某个状态的前缀后缀，我们只关心每个状态之间的关系，有一点动态规划中走楼梯问题的感觉。不过 KMP 算法似乎也不是查找子串效率最高的方法，在 《算法》第四版中还有一个 Boyer–Moore 算法。

这两天看 KMP 算法最大的感受就是，有时候我们思考复杂的问题（特别是自己没有理解的问题），比如一些数学题或者算法，最重要的是理清思绪，像解毛线团一样。先找到线头，然后沿着线索一步一步往下走，哪一步没搞懂就搞懂再往下走。如果只是一味地在 ”用力“ 思考，很可能想着想着就忘了想到哪了。总之就是不要毛躁，太着急太用力只是在对 ”毛线团“ 发脾气，对理解问题没什么意义。

参考文章

1. 有限状态机 – Wikipedia
2. 字符串匹配的KMP算法 – 阮一峰
3. KMP 算法的两种实现
4. 使用确定有限状态自动机解KMP算法
5. 《算法 第四版》
6. 如何更好地掌握KMP算法