先吐個槽吧，公司也有這個算法，看了半天也不知道干什麼呢，寫的非常復雜，偶然的發現一個算法，小巧而精密，下面詳細敘述：
* 可以匹配0個或0個以上的字符
？可以匹配一個字符
這個算法應用的是遞歸的算法，開始擔心如果字符串過長的話，會因遞歸引起棧的溢出，還好在網上查了一下，win32默認的遞歸棧大小是2M，這足以進行很長字符串的匹配。
下面是核心的代碼，思路都在代碼的注釋中，下面給出代碼：
[cpp]
#include<iostream>
#include<string>
using namespace std;
bool match(char *pattern, char *content) {
// if we reatch both end of two string, we are done
if ('\0' == *pattern && '\0' == *content)
return true;
/* make sure that the characters after '*' are present in second string.
this function assumes that the first string will not contain two
consecutive '*'*/
if ('*' == *pattern && '\0' != *(pattern + 1) && '\0' == *content)
return false;
// if the first string contains '?', or current characters of both
// strings match
if ('?' == *pattern || *pattern == *content)
return match(pattern + 1, content + 1);
/* if there is *, then there are two possibilities
a) We consider current character of second string
b) We ignore current character of second string.*/
if ('*' == *pattern)
return match(pattern + 1, content) || match(pattern, content + 1);
return false;
}
void test(char *pattern, char *content) {
if (NULL == pattern || NULL == content)
puts("no");
match(pattern, content) ? puts("yes") : puts("no");
}
int main(int argc, char *argv[]) {
test("g*ks", "geeks"); // Yes
test("ge?ks*", "geeksforgeeks"); // Yes
test("g*k", "gee"); // No because 'k' is not in second
test("*pqrs", "pqrst"); // No because 't' is not in first
test("abc*bcd", "abcdhghgbcd"); // Yes
test("abc*c?d", "abcd"); // No because second must have 2 instances of 'c'
test("*c*d", "abcd"); // Yes
test("*?c*d", "abcd"); // Yes
cin.get();
return 0;
}
#include<iostream>
#include<string>
using namespace std;
bool match(char *pattern, char *content) {
// if we reatch both end of two string, we are done
if ('\0' == *pattern && '\0' == *content)
return true;
/* make sure that the characters after '*' are present in second string.
this function assumes that the first string will not contain two
consecutive '*'*/
if ('*' == *pattern && '\0' != *(pattern + 1) && '\0' == *content)
return false;
// if the first string contains '?', or current characters of both
// strings match
if ('?' == *pattern || *pattern == *content)
return match(pattern + 1, content + 1);
/* if there is *, then there are two possibilities
a) We consider current character of second string
b) We ignore current character of second string.*/
if ('*' == *pattern)
return match(pattern + 1, content) || match(pattern, content + 1);
return false;
}
void test(char *pattern, char *content) {
if (NULL == pattern || NULL == content)
puts("no");
match(pattern, content) ? puts("yes") : puts("no");
}
int main(int argc, char *argv[]) {
test("g*ks", "geeks"); // Yes
test("ge?ks*", "geeksforgeeks"); // Yes
test("g*k", "gee"); // No because 'k' is not in second
test("*pqrs", "pqrst"); // No because 't' is not in first
test("abc*bcd", "abcdhghgbcd"); // Yes
test("abc*c?d", "abcd"); // No because second must have 2 instances of 'c'
test("*c*d", "abcd"); // Yes
test("*?c*d", "abcd"); // Yes
cin.get();
return 0;
}
