regex - 检查两个模式是否相互匹配？

Question

This Leetcode problem是关于如何尽可能有效地将模式字符串与文本字符串进行匹配。模式字符串可以由字母、点和星号组成，其中字母仅匹配自身，点匹配任何单个字符，星号匹配前面字符的任意数量的副本。例如，模式

ab*c.

将匹配 ace 和 abbbbcc。我知道可以使用动态规划来解决这个原始问题。

我的问题是是否有可能查看两个模式是否相互匹配。例如，模式

bdbaa.*

可以匹配

bdb.*daa

是否有解决这种模式对模式匹配问题的好算法？

Answer 1

这是一种在多项式时间内有效的方法。它有点重量级，但可能有更有效的解决方案。

我认为对这里有帮助的第一个观察是重构问题。与其问这些模式是否彼此匹配，不如问这个等价的问题:

Given patterns P1 and P2, is there a string w where P1 and P2 each match w?

换句话说，我们将搜索每个模式都匹配的字符串，而不是试图让两个模式相互匹配。

您可能已经注意到，您可以使用的模式类型是正则表达式的子集。这很有用，因为对于您可以使用正则表达式及其属性可以做什么，有一个非常详尽的理论。因此，与其针对您原来的问题，不如解决这个更一般的问题:

Given two regular expressions R1 and R2, is there a string w that both R1 and R2 match?

解决这个更普遍的问题的原因是它使我们能够使用围绕正则表达式发展起来的理论。例如，在形式语言理论中，我们可以谈论正则表达式的语言，它是正则表达式匹配的所有字符串的集合。我们可以表示这个 L(R)。如果有一个字符串与两个正则表达式 R1 和 R2 匹配，那么该字符串同时属于 L(R1) 和 L(R2)，所以我们的问题等同于

Given two regexes R1 and R2, is there a string w in L(R1) ∩ L(R2)?

到目前为止，我们所做的只是重构我们想要解决的问题。现在让我们去解决它。

这里的关键步骤是可以将任何正则表达式转换为 NFA(不确定的有限自动机)，以便 NFA 接受正则表达式匹配的每个字符串，反之亦然。更好的是，生成的 NFA 可以在多项式时间内构建。因此，让我们从为每个输入正则表达式构建 NFA 开始。

现在我们有了这些 NFA，我们想回答这个问题:是否存在两个 NFA 都接受的字符串？幸运的是，有一种快速的方法可以回答这个问题。 NFA 上有一个常见的结构，称为乘积结构，给定两个 NFA N1 和 N2，构造一个新的 NFA N'，它接受 N1 和 N2 都接受的所有字符串，而不接受其他字符串。同样，此构造在多项式时间内运行。

一旦我们有了 N'，我们基本上就完成了!我们所要做的就是对 N' 的状态运行广度优先或深度优先搜索，看看是否找到接受状态。如果是这样，太好了!也就是说有一个字符串被N'接受了，也就是说有一个字符串被N1和N2都接受了，也就是说有一个字符串被R1和R2都匹配了，所以原题的答案是“是!”相反，如果我们无法达到接受状态，那么答案是“不，这是不可能的。”

我确信有一种方法可以通过对自动机 N' 进行某种隐式 BFS 而无需实际构造它来隐式地完成所有这些操作，并且应该可以在类似时间 O(n<支持>2)。如果我有更多时间，我会重新审视这个答案并详细说明如何做到这一点。