今天我们用状态机的思维来理解KMP。
KMP的关键我总结了一句话就是：
1 | “当发生错配时，如何 最大化 的利用之前匹配好的字符串，将它们的一部分作为新的前缀继续参与匹配” |
我们后面会详细用例子解释这句话。
状态机可以看成一个能不停的，不断的一次一次输入字符的机器，并显随着每一次的输入，自身的状态会实时变化。
状态机完全由模式串决定，模式串就像滔滔流水流过状态机，状态机和模式串完全没有关系。
比如有一个很长的匹配串，然后有一个模式串ABABAC，为了得到状态机的内部结构，我们可以完全不看匹配串。直接由模式串得到唯一确定的状态机。（至于是怎么得到的，我们后面讲）
1 | ABABAC |
这个状态机里有六个状态，他表示匹配进度，当状态标志为0的时候表示当前匹配进度为0，也就是一个字符都没有匹配上。当状态标志为3的时候就表示此时此刻已经有连续的三个字符说对了（并且这连续的三个字符是从头部开始算的），如果状态标志为6，就是此时此刻已经有连续的六个字符都说对了，匹配完成了。
1 | 跟着例子走一遍 |
由此我们可以推出，当不断的有新的字符输入状态机的时候，如果说对了，状态标志就增加1，如果说错了，状态标志就会减少，可能会减少1，有可能直接减少到0，也有可能原地不动没有变化，也就是减少0。
关键在于减少的情况很不确定，减少具体意味着什么，我们应该让状态机减小多少，这是这个算法的关键。
减小就意味着发生了错配，我们刚刚开头说了：
1 | “当发生错配时，如何 最大化 的利用之前匹配好的字符串，将它们的一部分作为新的前缀继续参与匹配” |
如果没有这句话，我们的直觉可能是，如果匹配错误了，直接把状态拨到0重新开始匹配不就可以了吗？
然而这个直觉错了，他会导致我们漏掉东西！
举一个简单的例子：
1 | 了解了解B站 |
匹配串
1 | 了解了解了解B站 |
所以了和B错配的时候不应该回到最前面，就漏了一个“了解”作为前缀。
所以要怎么构建这个状态机的内部结构呢？
1 | 手动构建一次 |