0

实现正则表达式匹配并支持“。” 和 '*'。

'。' 匹配任何单个字符。'*' 匹配零个或多个前面的元素。匹配应覆盖整个输入字符串（不是部分）。

一些例子：

isMatch(“aa”,”a”) → 假

isMatch(“aa”,”aa”) → 真

isMatch(“aaa”,”aa”) → 假

isMatch(“aa”, “a*”) → 真

isMatch(“aa”, “.*”) → 真

isMatch(“ab”, “.*”) → 真

isMatch(“aab”, “c*a*b”) → 真

作者给出了下面的解决方案，真的很漂亮。

bool isMatch(const char *s, const char *p) {
  assert(s && p);
  if (*p == '\0') return *s == '\0';

  // next char is not '*': must match current character
  if (*(p+1) != '*') {
    assert(*p != '*');
    return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
  }
  // next char is '*'
  while ((*p == *s) || (*p == '.' && *s != '\0')) {
    if (isMatch(s, p+2)) return true;
    s++;
  }
  return isMatch(s, p+2);
}

作者还给出了一些进一步的想法：

如果您仔细考虑，您可以利用上述代码以指数复杂度运行的某些情况。

你能想出一些例子吗？你如何让上面的代码更有效率？

我想出了一个需要很长时间才能得到结果的案例，而字符串 s 和 p 的长度并不大。

s[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" p[] ="a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a* a*a*a*a*a*a*b"

谁能帮我验证这个答案？如何看待这种寻找极端的测试题？

4

2 回答 2

2

这是一个经典案例，通过递归下降实现正则表达式匹配会导致病态行为。

实现这一点的正确方法是将您的正则表达式变成一个不确定的状态机。它需要（相当多）更多代码，但对于任何给定的正则表达式都会以线性时间运行。

这是关于该主题的一流文章。

干杯!

于 2012-09-18T04:09:03.930 回答
2

了解您的案例为何表现出指数行为的最佳原因是首先对代码进行一些试验，然后尝试从中收集一些经验数据并做出假设。

首先，让我们添加一些简单的“日志”：

#include <cassert> 
#include <cstdio>
using namespace std;

int count = 0;

bool isMatch(const char *s, const char *p) {
    printf("%5d   %s   %s\n", count++, s, p);  
    .
    .
    .

现在让我们进行一些实验，确保在每次实验之前重置计数（记住在实际代码中要避免使用全局变量 :)）

isMatch("a", "a*b");
isMatch("aa", "a*a*b");
isMatch("aaa", "a*a*a*b");
isMatch("aaaa", "a*a*a*a*b");
isMatch("aaaaa", "a*a*a*a*a*b");
isMatch("aaaaaa", "a*a*a*a*a*a*b");

您可以查看每个的输出，并查看为每个生成的行数，然后问自己“当我延长字符串时，递归调用的数量如何增长？” （经典经验算法分析！）

我在aaa这里为你做了这个案例：http: //ideone.com/8t2kS

你可以看到它花了 34 步。查看输出；它应该让您对匹配的性质有所了解。并尝试增加长度的字符串。快乐的实验。

于 2012-09-18T15:50:24.800 回答