最常见的通配符是?和*。其中，?可以代表一个字符（不能没有），*可以代表任意多个字符（可以为空）。
首先是?，根据?的功能，?表示任意字符，也就是说在匹配过程中，?永远匹配成功。本质上，?并没有修改算法，而仅仅修改了匹配规则——遇到?则一定匹配。
然而*与此不同，*的作用是匹配任意多个字符，显然我们不能简单的修改匹配过程而满足要求。如果我们重新思考*的作用，我们会发现*的另一个作用就是分割P串，即如果P=P1*P2，那么与其说*代表匹配任意多个字符，不如说P的匹配条件是在匹配P1子串后再匹配P2子串。
因此，可以写出带通配符的字符串匹配算法。
1 // 朴素字符串匹配
2 // @param src - 待匹配的字符串
3 // @param pattern - 模式字符串
4 bool match(const char* src, const char* pattern)
5 {
6 if(src == NULL || pattern == NULL) return false;
7
8 if(*pattern == '\0')
9 if(*src == '\0')
10 return true;
11 else
12 return false;
13 else if(*src == '\0')
14 return false;
15
16 int srcLen = strlen(src);
17 int patternLen = strlen(pattern);
18 if(patternLen > srcLen)
19 return false;
20 int i = 0, j = 0;
21 while(i < srcLen - patternLen && j < patternLen)
22 {
23 if(src[i + j] == pattern[j])
24 {
25 j++;
26 }else
27 {
28 i++;
29 j = 0;
30 }
31 }
32 if( j == patternLen)
33 return true;
34 return false;
35 }
36
37 // 带通配符的字符串匹配
38 // @param src - 待匹配的字符串
39 // @param pattern - 模式字符串
40 // 使用了伪递归，容易改成迭代形式
41 bool match2(const char* src, const char* pattern)
42 {
43 if(src == NULL || pattern == NULL) return false;
44
45 if(*pattern == '\0')
46 return true;
47 if(*src == '\0')
48 return false;
49
50 // 去除开头的'*'
51 const char* tmp_pat = pattern;
52 while (*tmp_pat && *tmp_pat == '*') tmp_pat++;
53
54 int srcLen = strlen(src);
55 int patternLen = strlen(tmp_pat);
56 if(patternLen > srcLen)
57 return false;
58 // 开始匹配，包括'?'的任意匹配，直到遇到模式中的'*'或匹配完为止。
59 int i = 0,j = 0;
60 while(i < srcLen - patternLen && j < patternLen && tmp_pat[j] != '*')
61 {
62 if(tmp_pat[j] == '?' || src[i+j] == tmp_pat[j])
63 j++;
64 else{
65 j = 0;
66 i++;
67 }
68 }
69 // 匹配成功
70 if(j == patternLen)
71 return true;
72 // 遇到'*'，开始下一次匹配
73 if (tmp_pat[j] == '*')
74 {
75 i+=j;
76 return match2(src + i, tmp_pat + j);
77 }
78
79 return false;
80 }
81
82 int main()
83 {
84 char* src = "wo shi yi ge zhong guo ren";
85 char* pat = "shi";
86 if (match(src, pat))
87 {
88 cout<<"match1\n";
89 }
90 char* pat2 = "*sh*?*";
91 if (match2(src, pat2))
92 {
93 cout<<"match2\n";
94 }
95 }
96