KMP字符串匹配算法(一)—用于模式匹配的有限自动机

KMP字符串匹配算法(一)—模式匹配

KMP算法基于对模式串P的预处理生成辅助数据结构，并通过该数据结构在主文本T中高效实现匹配过程。
这里的模式串P与主文本T均可被视为任何支持等值比较的对象集合。
通常情况下，在这种应用场景下模式串P的长度远小于主文本T的长度。

有限自动机

由于KMP算法与有限自动机存在很多共同的基础原因，并因此提及这一概念是有必要的。
为了在模式匹配中避免不必要的比较次数，并对模式串进行了预处理。
我认为学习自动机理论有助于掌握KMP算法的工作原理。

如图(a)所示的是一个有限自动机模型，在其中我们定义了字母表\sum为\{a,b,c\}；该自动机能够识别接受所有以"abaBaca"结尾且具有特定模式（如包含连续奇数个'a'）的字符串序列。
例如输入字符串"cbbBbccabaBaCa"时，则会经历一系列的状态转换过程：
从初始状态出发，
c→0,
b→0,
接着又回到初始状态，
然后依次经过多个中间状态，
最终若能到达终止状态，则表示该输入串被该自动机成功接受。

来自有限自动机的启发

在处理