前言
题目传送门 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\) ，有以下两种情况：
-
如果第 \(i+1\) 个通配符是 \(\texttt{?}\) ，则 \(dp_{i+1,j+len+1} = 1\) 。原因是匹配掉之间的串后，\(\texttt{?}\) 还可以多匹配一个字符。
-
如果第 \(i+1\) 个通配符是 \(\texttt{*}\) ，则 \(dp_{i+1,j+len}=dp_{i+1,j+len+1}=\cdots =dp_{i+1,m}\) 。原因是匹配掉之间的串后，\(\texttt{*}\) 还可以匹配任意个字符，一直到文本串末尾。
解决了核心的问题—— DP 转移方式，我们再来看几个细节问题。
-
如何处理输入？因为我们要对模式串分段，所以我们考虑按字符读入模式串。我们用
sign[]数组存储每个通配符是什么，用s[]数组存储每两个通配符之间的模式串。如果有连着的通配符，或第 \(0\) 个就是通配符，我们认为这一段是空串。 -
DP 必须按通配符分段转移，如果模式串末尾不是通配符怎么办？好办。我们人为的给模式串末尾加一个 \(\texttt{?}\) ，并给输入的文本串后加一个特殊字符就好。同时这样处理后 \(cnt\) 个通配符恰好把模式串分为 \(cnt\) 段，一一对应。
-
如何快速比较文本串的子串与模式串的一段是否相等？考虑使用哈希。我们预处理文本串的前缀哈希值，从而我们可以在 \(\mathcal O(1)\) 时间知道任何子串的哈希值；因为模式串只有一个，我们分完段后直接对每段求哈希值存起来就好。
综上，我们能够写出来第一份代码：
!!! note "code1.0"
```cpp
#include
#include
#include
#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;
}
```
!!!
这份代码能够通过 gxyzoj 的数据，但是并不能通过洛谷。究其原因，是遇到 \(\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;
}