regex - (简化的)正则表达式匹配的复杂性

Question

我只是想知道这个正则表达式匹配问题的复杂性:给定一串小写字母和一个匹配规则，判断该规则是否可以匹配整个字符串。该规则是一个简化的正则表达式，它只包含较小的字母和/或“。” (句点)和/或“*”(星号)。句点可以匹配任何小写字母，其中星号可以匹配零个或多个前面的元素。

这里有一些例子:

• isMatch("aa","a") 为假
• isMatch("aa","aa") 为真
• isMatch("aaa","aa") 为假
• isMatch("aa", "a*") 为真
• isMatch("aa", ".*") 为真
• isMatch("ab", ".*") 为真
• isMatch("aab", "c*a*b") 为真

据说这个问题可以在多项式时间内解决。我只是想知道如何。凭直觉，将“aaaaaaaaaa”与“.*a.*”之类的正则表达式匹配使得在与有限确定性机器匹配时很难确定状态转换。有什么意见吗？

谢谢。

Answer 1

您可以使用动态规划算法在多项式时间内解决此问题。这个想法是回答以下形式的查询:

Can you match the last m characters of the string using the last n characters of the regular expression?

想法是使用递归算法，然后要么内存结果，要么使用动态规划来缓存结果。递归算法的工作原理如下:

• 如果正则表达式为空，则只匹配空字符串。
• 如果正则表达式的第二个字符不是 *，则正则表达式匹配字符串当且仅当字符串的第一个字符匹配正则表达式并且字符串的其余部分匹配正则表达式的其余部分。
• 如果正则表达式的第二个字符是 *，则正则表达式匹配字符串当且仅当以下条件之一为真:
  • 正则表达式的第一个字符匹配字符串的第一个字符，同一个正则表达式匹配字符串的其余部分。
  • 正则表达式的第一个字符匹配字符串的第一个字符，去掉 *'ed 表达式的正则表达式匹配字符串的其余部分。
  • 正则表达式的第一个字符与字符串的第一个字符不匹配，但通过删除 *'ed 表达式形成的正则表达式与字符串匹配。

这些情况中的每一个都会进行递归调用，其中字符串或正则表达式更短并且 O(1) 除了递归调用之外的工作。由于只有 Θ(mn) 个可能的子问题(每个正则表达式的后缀和原始字符串的后缀的组合一个)，使用内存可以在 Θ(mn) 时间内解决这个问题。

希望这对您有所帮助!