有限状态自动机是一个编程的模型，有若干个状态，和一个状态转移的规则，首先你在一个初始状态上，然后外部会有一系列的输入，转移规则根据你所在的状态和输入确定你的下一步状态。如果规则只产生一个下一步状态，那就是确定有限状态机(dfa)。也有可能转移到多个状态，那就变成了非确定有限状态机了(nfa)。
我最先接触这个是通过正则表达式。一个正则表达式可以对应到一个nfa，*规则其实就是转移到原来状态并且无条件转移到下一个状态，.规则就是匹配任何一个字母，转移到下一个状态。
正则的匹配也可以通过搜索来完成，可是复杂度非常之高，状态机也可以看做是对搜索的一种剪枝优化，状态机的每一个状态对应搜索树的节点，相对于暴力搜索，状态机合并了一些子情况相同的节点从而节省了大量的时间。
后来我就重温了kmp，他是一种确定有限状态自动机，规则非常有意思：状态N有两种转移方式，一种转移到N＋1，另一种转移到m，满足0到N这个子串上头m个字符串和末尾m个字符串相等。两个字符串可以重叠，可是m不能是N因为当m和N相等，这两个字符串就是同一个字符串，并没有什么意义。
kmp有一个很神奇，也令我费解的地方，那就是构造自动机代码和转移状态的代码惊人相似，我觉得其中必有蹊跷。
有了上面的了解，就可以理解ac自动机了，kmp就是一个ac自动机的简化版，不同的是kmp中的结构是字符串，而ac自动机中的结构是字典树。kmp只能转移到自身的子串，而ac自动机可以转移到字典树上的别的串上去。所以构造起来比较复杂，使用上和kmp是一样一样的。