T2-15 通配符匹配

题意理解

给定文本串 $S$ 和模式串 $P$，其中 ? 匹配任意单个字符，* 匹配任意字符序列（包括空串）。判断 $P$ 能否完全匹配 $S$。

---

思路分析

使用动态规划。

设 $dp[i][j]$ 表示：$S$ 的前 $i$ 个字符和 $P$ 的前 $j$ 个字符是否匹配。

状态转移：

1. 若 $P[j-1]$ 是普通字符：

   $$dp[i][j] = dp[i-1][j-1] \land (S[i-1] = P[j-1])$$

2. 若 $P[j-1]$ 是 ?（匹配任意单个字符）：

   $$dp[i][j] = dp[i-1][j-1]$$

3. 若 $P[j-1]$ 是 *（匹配任意序列）：

   $$dp[i][j] = dp[i][j-1] \lor dp[i-1][j]$$

   • $dp[i][j-1]$：* 匹配空串
   • $dp[i-1][j]$：* 匹配至少一个字符

边界条件：

• $dp[0][0] = true$：空串匹配空模式
• $dp[0][j] = true$ 当且仅当 $P$ 的前 $j$ 个字符全是 *

答案： $dp[n][m]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;  // 最大字符串长度

char S[MAXN], P[MAXN];  // 文本串和模式串
bool dp[MAXN][MAXN];    // dp[i][j]表示S前i个字符和P前j个字符是否匹配

int main() {
    cin >> S >> P;  // 读入文本串和模式串
    
    int n = strlen(S), m = strlen(P);  // 获取长度
    
    dp[0][0] = true;  // 边界：空串匹配空模式
    
    for (int j = 1; j <= m; j++) {  // 边界：空文本串匹配P的前j个字符
        if (P[j - 1] == '*') {  // 只有全是*才能匹配空串
            dp[0][j] = dp[0][j - 1];
        }
    }
    
    for (int i = 1; i <= n; i++) {  // 枚举S的前i个字符
        for (int j = 1; j <= m; j++) {  // 枚举P的前j个字符
            if (P[j - 1] == '*') {  // *可以匹配任意序列
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];  // 匹配空串或匹配至少一个字符
            } else if (P[j - 1] == '?' || S[i - 1] == P[j - 1]) {  // ?匹配任意单字符，或字符相同
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    
    cout << (dp[n][m] ? 1 : 0) << endl;  // 输出答案
    return 0;
}