代码之家 › 专栏 › 技术社区 › Fihop

正则表达式匹配对“.”的支持和'*'[关闭]

string-matching recursion algorithm

Fihop · 技术社区 · 13 年前

Implement regular expression matching with support for â.â and â*â.

。匹配任何单个字符。*匹配前面的元素中的零个或多个。匹配应该覆盖整个输入字符串(而不是部分)。

一些例子:

isMatch(aa,a)false

isMatch(aa,aa)true

isMatch(aaa,aa)false

isMatch(aa,a*)为真

isMatch(aa,.*)true

isMatch(ab,.*)true

isMatch(aab,c*a*b)true

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

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[]=“aaaaaaaaaa” p[]=“a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*

有人能帮我核实一下这个答案吗? 如何看待这种发现极端的测试问题?

2 回复 | 直到 13 年前

Ray Toal 13 年前

要理解为什么你的案例表现出指数行为,最好的方法是首先对代码进行一些实验,然后尝试从中收集一些经验数据并做出假设。

首先,让我们添加一些简单的“日志记录”:

#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步。看看输出;它应该让你对匹配的本质有一些了解。并且一定要尝试增加长度的字符串。快乐的实验。