DFA 运行时间不是O(n)而是O(nm)
DFA running time is not O(n) but O(nm)
如果你有一个有 m 个节点的 DFA，并且你 运行 它在一个有 n 个字符的字符串上，在每一步你不仅要测试从上一步继承的状态，还要测试 DFA 的第一个状态再次。所以在字符串中的 m 个字符之后（假设 m < n）最坏的情况是你有 mn 个活动状态要测试（每个状态只需要一个查找来推进或被解雇）
举个例子，考虑a{l}b正则表达式（所有以a开头的单词重复l次，后面跟着a b），它的DFA有m = l + 1个节点。将它与 k>l 的字符串 a{k}b 匹配意味着您将遇到最坏的情况，即在字符串中的 l 个字符之后有 (m - 1) 个活动状态。
我错过了什么？或者文献是否挥手实际实施只关注理论问题，即知道给定的完整字符串（即不是其中一个子字符串）是否匹配正则表达式。
从我的立场来看运行一个NFA或DFA将花费O(nm)次（m是NFA或DFA中的节点数和n个字符）。唯一的问题是 NFA 比 DFA 有更多的节点。
从历史上看，DFA 最初被定义为匹配整个字符串而不是搜索子字符串，这就是为什么文献通常会谈论 DFA 的时间复杂度，即接受单个字符串然后返回是否是整个字符串字符串匹配与否。如果你有一个匹配整个字符串的 DFA 并且你想用它来搜索子字符串，那么你本质上是 运行DFA 多次，每个可能的开始位置一次，这就是为什么你将 O(mn) 作为您的 运行 时间而不是 O(n)。
但是，如果您的目标是匹配某处的子字符串，那么重新设计 DFA 可能会更好。例如，假设您想使用 DFA 匹配一些正则表达式 R。与其为 R 构建 DFA 并 运行 从每个可能的位置开始，不如为正则表达式 Σ* R Σ* 构建 DFA。现在，如果输入的任何子字符串与 R 匹配，则整个字符串与 Σ* R Σ * 匹配，因此您只需要 运行 DFA 对字符串进行一次传递。这将 运行 时间减少到 O(n)，因为你只是 运行 一次通过。
如果您真的有一个 DFA，您将不会有多个活动状态。 DFA 被定义为只有一个活动状态。而每个角色只能导致恰好是下一个状态。
如果你取这个属性，你从起始状态开始，消耗n个字符。在您检查的每个字符处：
- 如果没有过渡到非错误状态 => 不匹配
- 如果转换到非错误状态 => 继续
最后检查您的当前状态是否为最终状态。如果是 => 成功，否则 => 不匹配。
从我的角度来看，NFA 需要 O(n*m)，而 DFA 需要 O(n)。 DFA 性能不依赖于模式复杂性（节点数）。
但我不知道为什么你接受了一个涉及使用 DFA 进行字符串搜索（确实不是 O(n)）而不是使用 DFA 进行字符串匹配的答案。但如果这是你的问题：有些算法是从 DFA 派生出来的，比搜索 ΣRΣ 做得更好，这就是 Knuth-Morris-Pratt（对于单一模式）和 Aho-Corasick（多种模式）。底层 DFA 是压缩的，但两种算法共享 属性 它们只为一个字符执行一次转换，而在任何时候都没有多个状态（就像在 NFA 中一样）。
如果你有一个有 m 个节点的 DFA，并且你 运行 它在一个有 n 个字符的字符串上，在每一步你不仅要测试从上一步继承的状态，还要测试 DFA 的第一个状态再次。所以在字符串中的 m 个字符之后（假设 m < n）最坏的情况是你有 mn 个活动状态要测试（每个状态只需要一个查找来推进或被解雇）
举个例子，考虑a{l}b正则表达式（所有以a开头的单词重复l次，后面跟着a b），它的DFA有m = l + 1个节点。将它与 k>l 的字符串 a{k}b 匹配意味着您将遇到最坏的情况，即在字符串中的 l 个字符之后有 (m - 1) 个活动状态。
我错过了什么？或者文献是否挥手实际实施只关注理论问题，即知道给定的完整字符串（即不是其中一个子字符串）是否匹配正则表达式。
从我的立场来看运行一个NFA或DFA将花费O(nm)次（m是NFA或DFA中的节点数和n个字符）。唯一的问题是 NFA 比 DFA 有更多的节点。
从历史上看，DFA 最初被定义为匹配整个字符串而不是搜索子字符串，这就是为什么文献通常会谈论 DFA 的时间复杂度，即接受单个字符串然后返回是否是整个字符串字符串匹配与否。如果你有一个匹配整个字符串的 DFA 并且你想用它来搜索子字符串，那么你本质上是 运行DFA 多次，每个可能的开始位置一次，这就是为什么你将 O(mn) 作为您的 运行 时间而不是 O(n)。
但是，如果您的目标是匹配某处的子字符串，那么重新设计 DFA 可能会更好。例如，假设您想使用 DFA 匹配一些正则表达式 R。与其为 R 构建 DFA 并 运行 从每个可能的位置开始，不如为正则表达式 Σ* R Σ* 构建 DFA。现在，如果输入的任何子字符串与 R 匹配，则整个字符串与 Σ* R Σ * 匹配，因此您只需要 运行 DFA 对字符串进行一次传递。这将 运行 时间减少到 O(n)，因为你只是 运行 一次通过。
如果您真的有一个 DFA，您将不会有多个活动状态。 DFA 被定义为只有一个活动状态。而每个角色只能导致恰好是下一个状态。
如果你取这个属性，你从起始状态开始，消耗n个字符。在您检查的每个字符处： - 如果没有过渡到非错误状态 => 不匹配 - 如果转换到非错误状态 => 继续
最后检查您的当前状态是否为最终状态。如果是 => 成功，否则 => 不匹配。
从我的角度来看，NFA 需要 O(n*m)，而 DFA 需要 O(n)。 DFA 性能不依赖于模式复杂性（节点数）。
但我不知道为什么你接受了一个涉及使用 DFA 进行字符串搜索（确实不是 O(n)）而不是使用 DFA 进行字符串匹配的答案。但如果这是你的问题：有些算法是从 DFA 派生出来的，比搜索 ΣRΣ 做得更好，这就是 Knuth-Morris-Pratt（对于单一模式）和 Aho-Corasick（多种模式）。底层 DFA 是压缩的，但两种算法共享 属性 它们只为一个字符执行一次转换，而在任何时候都没有多个状态（就像在 NFA 中一样）。