有限自动机字符串匹配器
Finite Automata String Matcher
我正在尝试使用 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
在内部 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，只增加一个字符。
我正在尝试使用 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
在内部 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，只增加一个字符。