有限自动机模式匹配

Question

最近，我正在阅读著名的算法设计书籍CLRS(Cormen，Leiserson，Ri背心，Stain，第三版).在经典的KMP算法和Rabin算法之间，有一部分是关于有限自动机的字符串匹配。因此，算法根据模式创建自动机，并开始对字符串进行处理。

​

因此，在这个例子中，算法搜索输入字符串中的模式"ababaca“。所以对我来说，除了两件事之外，一切都是合乎逻辑的。

当我到达"b“时，为什么没有从4状态到以前状态的路径，因为在这种情况下，我将拥有”a“，这已经是一种错配？当我从6州读"b“或"c”时会发生什么？？有什么是我误解的吗？也没有从状态0到4的"c“大小写，等等。

Answer 1

检查表(b)。您所说的所有状态都标记为0。所以你要回到起点。在图像中，你会得到很多边缘回到0，这样它们就不会显示出来(为了清晰起见)。