简单正则表达式匹配
题目仍然来自于leetcode.com，“写一个只包含.和*的正则表达式匹配程序”。
类似的题目在摩根士丹利面试时遇到过，当时的要求是?和+。在现在看来，我当时写的程序是错误的。我当时的思路是这样的：匹配时向前展望一位，如果遇到特殊符号?和+就一直匹特殊符号前一位直到失败。这样的算法在遇到模式串为ab+bc，待匹配串为abbbc时，答案是匹配失败，显然正确答案应该是匹配的。错误的原因在于，没有考虑到特殊符号后面可能会有与特殊符号前的字符相同的字符。正确的方法是应该暴力枚举所有可能匹配情况。下面的程序是正确的解法：
1 static int recursive_simple_regex_match(const char* s, const char* p) 2 { 3 int res; 4 if (*p == '\0') { 5 res = (*s == '\0'); 6 } 7 else { 8 if (*(p + 1) == '*') { 9 if (*p == '*') { 10 res = -1; 11 } 12 else { 13 res = 0; 14 while (((*p != '.') && (*p == *s)) || ((*p == '.') && (*s != '\0'))) { 15 if (recursive_simple_regex_match(s, p + 2) > 0) { 16 res = 1; 17 break; 18 } 19 s++; 20 } 21 } 22 } 23 else { 24 if (((*p != '.') && (*p == *s)) || ((*p == '.') && (*s != '\0'))) { 25 res = recursive_simple_regex_match(s + 1, p + 1); 26 } 27 else { 28 res = 0; 29 } 30 } 31 } 32 return res; 33 } 34 35 int simple_regex_match(const char* s, const char* p) 36 { 37 if (s == NULL || p == NULL) { 38 return -1; 39 } 40 if (*p == '*') { 41 return -1; 42 } 43 return recursive_simple_regex_match(s, p); 44 }
关于完整的正则表达式的匹配，通用的解决方案是将正则表达式转换为相应的确定有限自动机，然后利用该自动机进行匹配。
优质内容筛选与推荐>>1、angularjs-ui-router-animation
2、二叉堆，优先队列，二叉树的理解
3、TestLink学习二：Windows搭建TestLink环境
4、ActiveMQ queue 代码示例
5、SQL注入浅水攻防