Luogu P3167 [CQOI2014] 通配符匹配 题解

前言

题目传送门 Luogu P3167 [CQOI2014] 通配符匹配

一道字符串 + DP 好题。

题意

最常见的通配符有两个，一个是星号（*），可以匹配 0 个及以上的任意字符；另一个是问号（?），可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

思路

首先，我们需要有一个大致的方向。我们可以考虑把输入按照通配符分段，然后用每一段模式串去尝试匹配文本串，匹配完一段后，根据它后面的通配符情况考虑怎么转移到下一段去。

容易看出，如果前面的一段已经匹配好了，那么后面的可以直接接着处理，而不用关心前面的具体是怎么匹配的。这启示我们也许可以考虑 DP 。

我们不妨设 \(dp_{i,j}\) 表示用模式串的第 \(i\) 个通配符及其之前的所有字符去匹配文本串的前 \(i\) 个字符的可行性。\(dp_{i,j}=1\) 说明可行，反之不可行。注意这里的表述，【前 \(i\) 个字符】和【第 \(i\) 个字符】是不同的，具体地，第 \(0\) 个字符等价于前 \(1\) 个字符。

然后我们考虑状态转移。假设当前的状态是 \(dp_{i,j}=1\) ，当前位置匹配好了，那么当【从第 \(i\) 个通配符到第 \(i+1\) 个通配符之间文本串和模式串】相等时，我们就可以从当前位置出发往后递推。设他们之间的这个串长度为 \(len\) ，文本串总长度为 \(m\) ，有以下两种情况：

1. 如果第 \(i+1\) 个通配符是 \(\texttt{?}\) ，则 \(dp_{i+1,j+len+1} = 1\) 。原因是匹配掉之间的串后，\(\texttt{?}\) 还可以多匹配一个字符。

2. 如果第 \(i+1\) 个通配符是 \(\texttt{*}\) ，则 \(dp_{i+1,j+len}=dp_{i+1,j+len+1}=\cdots =dp_{i+1,m}\) 。原因是匹配掉之间的串后，\(\texttt{*}\) 还可以匹配任意个字符，一直到文本串末尾。

解决了核心的问题—— DP 转移方式，我们再来看几个细节问题。

1. 如何处理输入？因为我们要对模式串分段，所以我们考虑按字符读入模式串。我们用 sign[] 数组存储每个通配符是什么，用 s[] 数组存储每两个通配符之间的模式串。如果有连着的通配符，或第 \(0\) 个就是通配符，我们认为这一段是空串。

2. DP 必须按通配符分段转移，如果模式串末尾不是通配符怎么办？好办。我们人为的给模式串末尾加一个 \(\texttt{?}\) ，并给输入的文本串后加一个特殊字符就好。同时这样处理后 \(cnt\) 个通配符恰好把模式串分为 \(cnt\) 段，一一对应。

3. 如何快速比较文本串的子串与模式串的一段是否相等？考虑使用哈希。我们预处理文本串的前缀哈希值，从而我们可以在 \(\mathcal O(1)\) 时间知道任何子串的哈希值；因为模式串只有一个，我们分完段后直接对每段求哈希值存起来就好。

综上，我们能够写出来第一份代码：

code1.0

#include<iostream>
#include<cstring>
#include<string>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ull unsigned long long
#define MIKU 0
using namespace std;

const ull P = 131;

int n, cnt;
char sign[15];
string s[15];
ull v[15], h[100005], p[100005];
bool dp[15][100005];

ull get_hash(string s) {
	ull res = 0;
	int len = s.size();
	for(int i=0; i<len; i++) res = res * P + s[i];
	return res;
}

void pre(string s) {
	int len = s.size();
	h[1] = s[0];
	for(int i=2; i<=len; i++) h[i] = h[i-1] * P + s[i-1];
}

bool check(string str) {
	dp[0][0] = 1;
	int len = str.size();
	for(int j=0; j<len; j++) {
		for(int i=0; i<=cnt; i++) {
			if(!dp[i][j]) continue;
			ull v2 = h[j+s[i+1].size()] - h[j] * p[s[i+1].size()];
			if(v2 == v[i+1]) {
				if(sign[i+1] == '?') dp[i+1][j+s[i+1].size()+1] = 1;
				else for(int k=j+s[i+1].size(); k<=len; k++) dp[i+1][k] = 1;
			}
		}
	}
	return dp[cnt][len];
}

int main() {
	char ch = getchar();
	string str = "";
	while(ch != '\n') {
		if(ch == '*' || ch == '?') sign[++cnt] = ch, ch = getchar(), s[cnt] = str, str = "";
		else str += ch, ch = getchar();
	}
	sign[++cnt] = '?';
	if(str.size()) s[cnt] = str;
	cin>>n;
	for(int i=1; i<=cnt; i++) v[i] = get_hash(s[i]);
	p[0] = 1;
	for(int i=1; i<=100000; i++) p[i] = p[i-1] * P;
	for(int i=1; i<=n; i++) {
		memset(h, 0, sizeof(h)), memset(dp, 0, sizeof(dp));
		cin>>str;
		str += '%';
		pre(str);
		if(check(str)) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return MIKU;
}

然而到这里并不能通过洛谷数据。究其原因，是遇到 \(\texttt{*}\) 时的转移

for(int k=j+s[i+1].size(); k<=len; k++) 
    dp[i+1][k] = 1;

是 \(\mathcal O(len)\) 的，太慢了。我们需要考虑如何将这个转移优化到 \(\mathcal O(1)\) 。

我们观察到这个循环是从 \(dp_{i+1,j+s[i+1].size}\) 遍历到 \(dp_{i+1,len}\) 的，而这部分本来在枚举状态的时候就必须遍历到。我们不妨把这个循环均摊到外层中。我们引入一个标记数组 \(tag_{i,j}\) 。若 \(tag_{i,j}=1\) ，表示 \(dp_{i,j}\) 这个状态是可以被上一个 \(\texttt{*}\) 通配的，那么我们直接更新下一个位置 \(dp_{i,j+1}=1,tag_{i.j+1}=1\) 。因为 \(\texttt{*}\) 可以通配任意多个字符，可以一直向下延伸。若 \(tag_{i,j}=0\) 则不管。这样，每循环到一个位置只更新一个位置，复杂度就会降低一个 \(len\) 。

加上这个小优化，我们就能写出最终代码。

代码

#include<iostream>
#include<cstring>
#include<string>
#define ull unsigned long long
#define MIKU 0
using namespace std;

const ull P = 131;

int n, cnt;
char sign[15];
string s[15];
ull v[15], h[100005], p[100005];
bool dp[15][100005], tag[15][100005];

ull get_hash(string s) {
	ull res = 0;
	int len = s.size();
	for(int i=0; i<len; i++) res = res * P + s[i];
	return res;
}

void pre(string s) {
	int len = s.size();
	h[1] = s[0];
	for(int i=2; i<=len; i++) h[i] = h[i-1] * P + s[i-1];  //注意这里转换了一下下标，因为前 i 个是第 i-1 个。
}

bool check(string str) {
	dp[0][0] = 1;  //注意初始化。文本串前 0 个与模式串前 0 个一定能匹配。
	int len = str.size();
	for(int j=0; j<len; j++) {
		for(int i=0; i<=cnt; i++) {
			if(!dp[i][j]) continue;
			ull v2 = h[j+s[i+1].size()] - h[j] * p[s[i+1].size()];
			if(v2 == v[i+1]) {
				if(sign[i+1] == '?') dp[i+1][j+s[i+1].size()+1] = 1;
				else dp[i+1][j+s[i+1].size()] = 1, tag[i+1][j+s[i+1].size()] = 1;
			}
			if(tag[i][j]) dp[i][j+1] = 1, tag[i][j+1] = 1;  //优化
		}
	}
	return dp[cnt][len];
}

int main() {
	char ch = getchar();
	string str = "";
	while(ch != '\n') {
		if(ch == '*' || ch == '?') sign[++cnt] = ch, ch = getchar(), s[cnt] = str, str = "";
		else str += ch, ch = getchar();
	}
	sign[++cnt] = '?';  //尾部处理
	if(str.size()) s[cnt] = str;
	cin>>n;
	for(int i=1; i<=cnt; i++) v[i] = get_hash(s[i]);
	p[0] = 1;
	for(int i=1; i<=100000; i++) p[i] = p[i-1] * P;
	for(int i=1; i<=n; i++) {
		memset(h, 0, sizeof(h));
		memset(dp, 0, sizeof(dp)), memset(tag, 0, sizeof(tag));
		cin>>str;
		str += '%';  //加一个特殊字符
		pre(str);  //预处理前缀哈希
		if(check(str)) cout<<"YES\n";
		else cout<<"NO\n";
	} 
	return MIKU;
}