带通配符的字符串匹配

发表于 | Edited on | 分类于 | 次阅读

题目来源： http://noi.openjudge.cn/ch0206/6252/

题目描述

通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。

你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。

例如，1?456 可以匹配 12456、13456、1a456，但是却不能够匹配23456、1aa456；
2*77?8可以匹配 24457798、237708、27798。

解题思路

使用动态规划，即可，但是’*‘可以代表空字符串，一个字符串和多个字符串，所以遇到’*'的时候需要额外的处理。
假设F[i][j]表示长度为i第一个字符串X和长度为j的第二个字符串Y进行匹配，长度为i对应的字符是X[i-1]（字符串下标从0开始计算）,长度为j对应于Y的字符Y[j-1]。

  • 如果X[i-1]是’?‘，那么F[i][j] = F[i-1][j-1], 因为’?'可以匹配任意单个字符。
  • 如果X[i-1]是‘*’，由于’*'可以表示任意多个字符，所以此时对应关系为：
    • F[i][j] = F[i-1][j] || F[i-1][j-1]||F[i][j-1] ;三个关系式分别对应’*'表示0、1、多个字符。
  • 如果X[i-1]是普通字符，F[i][j] = X[i-1] == Y[j-1];

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
using namespace std;

string match(const string& str1, const string& str2) {

	vector<vector<bool>> F(str1.size() + 1, vector<bool>(str2.size() + 1, false));
	// 这里用于初始化，F[0][0] = true;F[i][0]是否为true需要看X[i-1]是否为'\*'
	F[0][0] = true;
	for (int i = 1; i <= str1.size(); ++i) {
		if (str1[i - 1] == '*')
			F[i][0] = F[i - 1][0];
	}

	// F[i][j]表示长度为i的str1和长度为j的str2是否匹配
	for (int i = 1; i <= str1.size(); ++i) {
		for (int j = 1; j <= str2.size(); ++j) {
			if (str1[i - 1] == '?' || str1[i - 1] == str2[j - 1])
				F[i][j] = F[i - 1][j - 1];
			else if (str1[i - 1] == '*') {
				F[i][j] = F[i - 1][j] || F[i][j - 1] || F[i - 1][j - 1];
			}
			else {
				F[i][j] = false;
			}
		}
	}
	if (F[str1.size()][str2.size()])
		return "matched";
	else
		return "not matched";
}

int main() {
    // 加了下面两句速度反而变慢了？ shit
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);
	cout << match(str1, str2) << endl;
}