如何在C或C ++中编写简单的正则表达式模式匹配函数？
这是我今天的论文测试中的一个问题，函数签名是
int is_match(char* pattern,char* string) 该模式仅限于ASCII字符和量化*和? ，所以它相对简单。 如果匹配则is_match应返回1，否则返回0。
我该怎么做呢？
Brian Kernighan提供了一篇关于A正则表达式匹配器的简短文章， Rob Pike写了这篇文章，作为他们正在研究的一本书的演示程序。 这篇文章是一篇非常好的读物，解释了一般的代码和正则表达式。
我已经使用了这段代码，进行了一些更改以尝试一些扩展，例如还返回模式匹配的字符串中的位置，以便可以从原始文本复制匹配模式的子字符串。
来自文章：
我向Rob建议我们需要找到最小的正则表达式包来说明基本的想法，同时仍然认识到一个有用的和非平凡的模式类。 理想情况下，代码适合单个页面。
Rob消失在他的办公室里，至少在我现在记得的时候，在不超过一两个小时的时间内出现了30行C代码，随后出现在TPOP的第9章中。 该代码实现了一个处理这些结构的正则表达式匹配器：
c matches any literal character c . matches any single character ^ matches the beginning of the input string $ matches the end of the input string * matches zero or more occurrences of the previous character这是一个非常有用的课程; 根据我自己在日常使用正则表达式的经验，它很容易占所有实例的95％。 在许多情况下，解决正确的问题是迈向美好计划的重要一步。 Rob从选择范围广泛，非常小但重要，定义明确且可扩展的function集中选择得如此明智，值得称赞。
Rob的实现本身就是一个美丽代码的极好例子：紧凑，优雅，高效和实用。 这是我见过的最好的递归示例之一，它展示了C指针的强大function。 虽然当时我们最感兴趣的是传达一个好的符号在使程序更易于使用和可能更容易编写方面的重要作用，但正则表达式代码也是一种很好的方式来说明算法，数据结构，测试，性能增强和其他重要主题。
文章中的实际C源代码非常好。
/* match: search for regexp anywhere in text */ int match(char *regexp, char *text) { if (regexp[0] == '^') return matchhere(regexp+1, text); do { /* must look even if string is empty */ if (matchhere(regexp, text)) return 1; } while (*text++ != '\0'); return 0; } /* matchhere: search for regexp at beginning of text */ int matchhere(char *regexp, char *text) { if (regexp[0] == '\0') return 1; if (regexp[1] == '*') return matchstar(regexp[0], regexp+2, text); if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text)) return matchhere(regexp+1, text+1); return 0; } /* matchstar: search for c*regexp at beginning of text */ int matchstar(int c, char *regexp, char *text) { do { /* a * matches zero or more instances */ if (matchhere(regexp, text)) return 1; } while (*text != '\0' && (*text++ == c || c == '.')); return 0; }
有关您无法提交的解决方案，请参阅此问题 。 有关如何实现更具可读性的说明，请参阅此文章 。
这是递归可扩展的实现。 测试了模式复杂性的第一顺序。
#include #include #include #include struct Match { Match():_next(0) {} virtual bool match(const char * pattern, const char * input) const { return !std::strcmp(pattern, input); } bool next(const char * pattern, const char * input) const { if (!_next) return false; return _next->match(pattern, input); } const Match * _next; }; class MatchSet: public Match { typedef std::vector Set; Set toTry; public: virtual bool match(const char * pattern, const char * input) const { for (Set::const_iterator i = toTry.begin(); i !=toTry.end(); ++i) { if ((*i)->match(pattern, input)) return true; } return false; } void add(Match * m) { toTry.push_back(m); m->_next = this; } ~MatchSet() { for (Set::const_iterator i = toTry.begin(); i !=toTry.end(); ++i) if ((*i)->_next==this) (*i)->_next = 0; } }; struct MatchQuestion: public Match { virtual bool match(const char * pattern, const char * input) const { if (pattern[0] != '?') return false; if (next(pattern+1, input)) return true; if (next(pattern+1, input+1)) return true; return false; } }; struct MatchEmpty: public Match { virtual bool match(const char * pattern, const char * input) const { if (pattern[0]==0 && input[0]==0) return true; return false; } }; struct MatchAsterisk: public Match { virtual bool match(const char * pattern, const char * input) const { if (pattern[0] != '*') return false; if (pattern[1] == 0) { return true; } for (int i = 0; input[i] != 0; ++i) { if (next(pattern+1, input+i)) return true; } return false; } }; struct MatchSymbol: public Match { virtual bool match(const char * pattern, const char * input) const { // TODO: consider cycle here to prevent unnecessary recursion // Cycle should detect special characters and call next on them // Current implementation abstracts from that if (pattern[0] != input[0]) return false; return next(pattern+1, input+1); } }; class DefaultMatch: public MatchSet { MatchEmpty empty; MatchQuestion question; MatchAsterisk asterisk; MatchSymbol symbol; public: DefaultMatch() { add(&empty); add(&question); add(&asterisk); add(&symbol); } void test(const char * p, const char * input) const { testOneWay(p, input); if (!std::strcmp(p, input)) return; testOneWay(input, p); } bool testOneWay(const char * p, const char * input) const { const char * eqStr = " == "; bool rv = match(p, input); if (!rv) eqStr = " != "; std::cout << p << eqStr << input << std::endl; return rv; } }; int _tmain(int argc, _TCHAR* argv[]) { using namespace std; typedef vector Strings; Strings patterns; patterns.push_back("*"); patterns.push_back("*hw"); patterns.push_back("h*w"); patterns.push_back("hw*"); patterns.push_back("?"); patterns.push_back("?ab"); patterns.push_back("a?b"); patterns.push_back("ab?"); patterns.push_back("c"); patterns.push_back("cab"); patterns.push_back("acb"); patterns.push_back("abc"); patterns.push_back("*this homework?"); patterns.push_back("Is this homework?"); patterns.push_back("This is homework!"); patterns.push_back("How is this homework?"); patterns.push_back("hw"); patterns.push_back("homework"); patterns.push_back("howork"); DefaultMatch d; for (unsigned i = 0; i < patterns.size(); ++i) for (unsigned j =i; j < patterns.size(); ++j) d.test(patterns[i].c_str(), patterns[j].c_str()); return 0; }
如果有什么不清楚，请问。
作弊。 使用#include 。
尝试列出一些有趣的测试用例：
is_match（“dummy”，“dummy”）应该返回true;
is_match（“dumm？y”，“dummy”）应该返回true;
is_match（“dum？y”，“dummy”）应该返回false;
is_match（“dum * y”，“dummy”）应该返回true;
等等 …
然后看看如何使更简单的测试通过，然后下一个…
没有测试过，实际编码或调试它，但这可能会让你开始……
for each character in the pattern if pattern character after the current one is * // enter * state while current character from target == current pattern char, and not at end get next character from target skip a char from the pattern else if pattern character after the current one is ? // enter ? state if current character from target == current pattern char get next char from target skip a char from the pattern else // enter character state if current character from target == current pattern character get next character from target else return false return true
无需正则表达式和有限状态机的全部function来解决此问题。 作为替代方案，存在相对简单的动态编程解决方案。
如果可以将子串字符串 [i..n-1]与子图案模式 [j，m-1]匹配，则匹配（i，j）为1，其中n和m是长度分别是字符串和模式 。 否则让匹配（i，j）为0。
基本案例是：
-
match（n，m）= 1，可以将空字符串与空模式匹配;
-
match（i，m）= 0，你不能将非空字符串与空模式匹配;
转换分为3种情况，具体取决于当前子模式是以字符后跟’*’开头，还是字符后跟’？’ 或者只是以一个没有特殊符号的字符开头。
#include #include #include int is_match(char* pattern, char* string) { int n = strlen(string); int m = strlen(pattern); int i, j; int **match; match = (int **) malloc((n + 1) * sizeof(int *)); for(i = 0; i <= n; i++) { match[i] = (int *) malloc((m + 1) * sizeof(int)); } for(i = n; i >= 0; i--) { for(j = m; j >= 0; j--) { if(i == n && j == m) { match[i][j] = 1; } else if(i < n && j == m) { match[i][j] = 0; } else { match[i][j] = 0; if(pattern[j + 1] == '*') { if(match[i][j + 2]) match[i][j] = 1; if(i < n && pattern[j] == string[i] && match[i + 1][j]) match[i][j] = 1; } else if(pattern[j + 1] == '?') { if(match[i][j + 2]) match[i][j] = 1; if(i < n && pattern[j] == string[i] && match[i + 1][j + 2]) match[i][j] = 1; } else if(i < n && pattern[j] == string[i] && match[i + 1][j + 1]) { match[i][j] = 1; } } } } int result = match[0][0]; for(i = 0; i <= n; i++) { free(match[i]); } free(match); return result; } int main(void) { printf("is_match(dummy, dummy) = %d\n", is_match("dummy","dummy")); printf("is_match(dumm?y, dummy) = %d\n", is_match("dumm?y","dummy")); printf("is_match(dum?y, dummy) = %d\n", is_match("dum?y","dummy")); printf("is_match(dum*y, dummy) = %d\n", is_match("dum*y","dummy")); system("pause"); return 0; }
该方法的时间复杂度为O（n * m）。 存储器复杂度也是O（n * m），但是简单的修改可以减少到O（m）。
简单的递归实现。 这很慢但很容易理解：
int is_match(char *pattern, char *string) { if (!pattern[0]) { return !string[0]; } else if (pattern[1] == '?') { return (pattern[0] == string[0] && is_match(pattern+2, string+1)) || is_match(pattern+2, string); } else if (pattern[1] == '*') { size_t i; for (i=0; string[i] == pattern[0]; i++) if (is_match(pattern+2, string+i)) return 1; return 0; } else { return pattern[0] == string[0] && is_match(pattern+1, string+1); } }
希望我没事。
用于查找索引的AC程序，主字符串中的子字符串将从该索引开始。 在此处输入代码
#include int mystrstr (const char *,const char *); int mystrcmp(char *,char *); int main() { char *s1,*s2;//enter the strings, s1 is main string and s2 is substring. printf("Index is %d\n",mystrstr(s1,s2)); //print the index of the string if string is found } //search for the sub-string in the main string int mystrstr (const char *ps1,const char *ps2) { int i=0,j=0,c=0,l,m;char *x,*y; x=ps1; y=ps2; while(*ps1++)i++; while(*ps2++)j++; ps1=x; ps2=y; char z[j]; for(l=0;lps4[i]) return +1; else return -1; }
enter code here #include int mystrstr(char *,char *); int main() { char *s1="123bc123abcabcd1234wx",*s2="456"; int c =mystrstr(s1,s2); if(c==-1) printf("String is not found in the main string\n"); else printf("String starts from index: %d\n",c); } int mystrstr(char *ps1,char *ps2) { static int i=0,j=0; if(ps1[i]==ps2[j]&&ps2[j]!='\0') { i++;j++; return mystrstr(ps1,ps2); } else if(j!=0) { if(ps2[j]=='\0') return ij; else { j=0; return mystrstr(ps1,ps2); } } else if(ps1[i]=='\0') return -1; else { i++; return mystrstr(ps1,ps2); } }