有穷自动机的模式匹配

Question

最近在看著名的算法设计书CLRS(Cormen, Leiserson, Rivest, Stain, 3-rd edition)。在经典的 KMP 和 Rabin-Karp 算法之间，有一部分是关于字符串与有限自动机的匹配。因此算法根据模式创建自动机并开始处理字符串。

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

为什么当我到达 "b" 时没有从状态 4 到先前状态的路径，因为在那种情况下我将有 "ababb"，这已经是不匹配的了？？？？当我从状态 6 读取 "b" 或 "c" 时会发生什么？我有什么误解吗？也没有从状态 0 到 4 等读取 "c" 的情况..

Answer 1

检查table (b)。 你说的所有状态都标记为0。所以你回到开头。 在图像中，您会得到很多边缘回到 0，因此它们不会显示它们（为了清晰起见）。