首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7272

通配符匹配 给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。 其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’…

通配符匹配

给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。

其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’,‘abc’等字符串,但不可匹配‘ac’,‘aaac’等字符串 。

‘*’ 可以匹配任意长度字符串(包括空字符串),如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串,但不可匹配‘acb’,‘cac’等字符串。

两个字符串完全匹配才算匹配成功。

时间限制:2000

内存限制:262144

输入

输入为一个数字n表示测试字符串与字符模式对数,换行。(n ≤ 30) 后续2n行为每组匹配的s与p,每行字符串后换行。 s 非空,只包含从 a-z 的小写字母。 p 非空,只包含从 a-z 的小写字母,以及字符 ? 和 *。 字符串s和p的长度均小于50

输出

每一组匹配串匹配成功输出‘yes’,否则输出‘no’。

样例输入

3
abc
abc
abc
a*c
abc
a??c

样例输出

yes
yes
no
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;cstring&gt; using namespace std; bool isMatch(char* s, char* p) {     int m = strlen(s);     int n = strlen(p);     int i = 0; // s的指针     int j = 0; // p的指针     int star = -1; // 上一个星号的位置     int match = 0; // 上一个星号匹配到的位置     while (i &lt; m) {         if (j &lt; n &amp;&amp; (p[j] == '?' || s[i] == p[j])) { // '?'或者相等的情况             i++;             j++;         }         else if (j &lt; n &amp;&amp; p[j] == '*') { // '*'的情况             star = j; // 保存上一个星号的位置             match = i; // 保存当前匹配到的位置             j++; // p的指针向后移动一位         }         else if (star != -1) { // p中有星号,并且当前字符和p的字符不同,则回溯             j = star + 1; // p的指针回到上一个星号的下一位             match++; // 匹配位置向后移动一位             i = match; // s的指针回到上一个星号匹配到的位置的下一位         }         else { // 最后一种情况,匹配失败             return false;         }     }     while (j &lt; n &amp;&amp; p[j] == '*') { // 如果p中还有星号,则可以匹配空字符串         j++;     }     return j == n; // s和p都遍历完了才算匹配成功 } int main() {     int n; // 测试样例数     cin &gt;&gt; n;     char s[51]; // s的最大长度为50,再加上一个结束符'\0'     char p[51]; // p的最大长度为50,再加上一个结束符'\0'     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; s &gt;&gt; p;         if (isMatch(s, p)) {             cout &lt;&lt; "yes" &lt;&lt; endl;         }         else {             cout &lt;&lt; "no" &lt;&lt; endl;         }     }     return 0; }</pre>
这道题暂未补解析。