A40408. 通配符匹配给定一个字符串 s 和一个字符模式 p， 请实现一个支持'?'和'*'的通配符匹配功能。其中‘?’可以匹配任何单个字符， 如‘a?c’可以成功匹配‘aac’,‘abc’等字符串， 但不可匹配‘ac’,‘aaac’等字符串 。‘*’ 可以匹配任意长度字符串（包括空字符串） ,如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串， 但不可匹配‘acb’， ‘ca…
填空题
中等
知识点
题目描述
通配符匹配
给定一个字符串 s 和一个字符模式 p， 请实现一个支持'?'和'*'的通配符匹配功能。其中‘?’可以匹配任何单个字符， 如‘a?c’可以成功匹配‘aac’,‘abc’等字符串， 但不可匹配‘ac’,‘aaac’等字符串 。‘*’ 可以匹配任意长度字符串（包括空字符串） ,如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串， 但不可匹配‘acb’， ‘cac’等字符串。两个字符串完全匹配才算匹配成功。
输入
输入为一个数字 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
参考答案
#include <iostream>
#include <cstring>
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 < m) {
if (j < n && (p[j] == '?' || s[i] == p[j])) { // '?'或者相等的情况
i++;
j++;
}
else if (j < n && 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 < n && p[j] == '*') { // 如果p中还有星号，则可以匹配空字符串
j++;
}
return j == n; // s和p都遍历完了才算匹配成功
}
int main() {
int n; // 测试样例数
cin >> n;
char s[51]; // s的最大长度为50，再加上一个结束符'\0'
char p[51]; // p的最大长度为50，再加上一个结束符'\0'
for (int i = 0; i < n; i++) {
cin >> s >> p;
if (isMatch(s, p)) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
}
return 0;
}
上一题
下一题