java - 有限自动机字符串匹配器

Question

我正在尝试使用 java 构建 FA 字符串匹配器。我有以下伪代码。

要使有限自动机匹配器算法起作用，必须计算转换函数。以下算法 Compute-Transition-Function 计算给定模式 P 和字母表 sigma。

在上面的代码中，我无法理解 min(m + 1, q + 2) 是从哪里来的。(我确实理解为什么它是 k = min(m + 1, q + 2) 而不是 k = min(m, q + 1) 但为什么我们首先想要 m 和 q+1 中的最小值)

在第 5-7 行之间，它将 k 减 1，直到 Pk 成为 Pqa 的后缀，但我不明白 Pqa 代表什么。

另外，如何将第 8 行转换为 Java 代码？二维数组就足够了吗？还是我需要另一种数据结构。

相关问题:string matching with finite automata

Answer 1

在内部 repeat-until 循环中，假设我们有 Pq = 'abdab' 并且字符串是 'abdabcd'，我们的字母表是 abcd，我们正在为字母表中的每个符号寻找最佳替代方案，然后将转换存储到新状态。在上面的例子中，通过 'a'，我们应该移动到开头，'b' 移动到最开始，c 延长匹配，d 符号应该存储指向我们初始字符串中第三个符号的指针。所以 Pqa 应该读作 Pq 加上字母表中的字符 a。

编辑为什么要min of (q+2 and m+1)，因为我们想向前执行一步，我们也想限制字符串的长度，这是显而易见的。为什么我们不能执行 q+3、+4？这是因为我们只添加了一个字符，不可能仅通过一个字符将最佳匹配从 q 扩展到 q+2,+3。