July面试整理系列--（3）

题目描述：

在一篇英文文章中查找指定的人名，人名使用二十六个英文字母（可以是大写或小写）、空格以及两个通配符组成（*、?），通配符“*”表示零个或多个任意字母，通配符“?”表示一个任意字母。
如：“J* Smi??” 可以匹配“John Smith” .

请用C语言实现如下函数：
void scan(const char* pszText, const char* pszName);
注：pszText为整个文章字符，pszName为要求匹配的英文名。
请完成些函数实现输出所有匹配的英文名，除了printf外，不能用第三方的库函数等。

下面使用c++实现的。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #include <string>
 8 #include <climits>
 9 using namespace std;
10 
11 /*
12 从文章的第一个字符开始往后匹配，匹配成功就输出，不成功就
13 继续往后匹配，复杂度O(M*N)
14 dfs
15 可以考虑加上记忆化:bool DP[i][j]表示i到结尾，以及j到结尾，a,b是否匹配
16 */
17 int enda;
18 bool match(string a,int sa,string b,int sb)
19 {
20     //匹配完成
21     if(sb == b.length())
22     {
23         enda = sa;
24         return true;
25     }
26     //未匹配完成
27     if(sa == a.length())
28     {
29         if(b[sb] == '*')
30         {
31             enda = sa;
32             return true;
33         }
34         return false;
35     }
36     if(b[sb] != '*' && b[sb] != '?')
37     {
38         if(a[sa] == b[sb])
39             return match(a,sa+1,b,sb+1);
40         return false;
41     }
42     else
43     {
44         if(b[sb] == '*')
45         {
46             return match(a,sa,b,sb+1)||match(a,sa+1,b,sb);
47         }
48         else
49         {
50             return match(a,sa+1,b,sb+1);
51         }
52     }
53 }
54 
55 void scan(string a,string b)
56 {
57     int sa = 0;
58     int sb = 0;
59 
60     int lena = a.length();
61     int lenb = b.length();
62 
63     while(sa < lena)
64     {
65         if(match(a,sa,b,0))
66         {
67             cout<<a.substr(sa,enda-sa);
68             return;
69         }
70         else
71         {
72             sa++;
73         }
74     }
75     return;
76 }
77 
78 int main()
79 {
80     string a = "J* Smi??";
81     string b = "John Smith";
82     scan(b,a);
83     return 0;
84 }