regex - KMP 和基于 Regex/DFA 的搜索之间的区别

Question

我对KMP（Knuth-Morris-Pratt）和Regex（基于 DFA）搜索之间的关系感到困惑。

我的想法是 KMP 不能使用正则表达式符号（例如，(A|B){2}C），因此它只能搜索“单个”字符串（例如，AC或BC，但不是AC|BC）。这是真的？

另一个问题，如果模式是单个字符串 ( ABABAC)，它们本质上是否使用相同？

Answer 1

事实上，KMP 有一种广义形式，即 FA（aho-corasick 算法）。使用通配符也很容易。IMO 您可以将正则表达式与 kmp 一起使用，但这并不容易。

Answer 2

似乎（95% 肯定）两种算法都应该做完全相同的事情，因为从字符串中的位置 i 移动到位置 p 的前缀末尾的步骤将与两个算法中的非确定性自动机相同状态，一个在前缀 p 之后，一个在字符串的位置 i 处。一旦转换为 dfa，该自动机将具有一个模拟 NFA 的状态，并将在线性时间内完成。所以带有kleene star的正则表达式相当于KMP。

Answer 3

KMP 不能使用正则表达式符号，因此它只能搜索“单个”字符串。这是真的？

是的。KMP是一种字符串搜索算法，而不是模式匹配算法。

另一个问题，如果模式是单个字符串（ABABAC），它们本质上是否使用相同的？

不，基于 DFA 的匹配不等同于 KMP 算法。然而，高级正则表达式匹配实现可能会使用 KMP 作为优化。