语言月赛 202406 通配符匹配

题意分析

我们定义两个字符是匹配的，当且仅当它们相等，或其中至少一个为字符 ?。

进一步地，定义两个字符串匹配，当且仅当它们长度相等，且所有对应位置的字符都是匹配的。

给定字符串 $s$ 和 $t$，你需要找出所有 $s$ 的子串 $s(l, r)$（长度等于 $t$），使得 $s(l, r)$ 和 $t$ 匹配。按 $l$ 从小到大的顺序输出所有合法的 $(l, r)$。

---

解题思路

本题要求判断 $s$ 的哪些子串与 $t$ 匹配。

由于 $|s|, |t| \leq 1000$，暴力枚举每个可能的子串，然后逐字符比较即可。

匹配规则：

• 若 $s[i] == t[i]$：匹配；
• 若 s[i] == '?' 或 t[i] == '?'：匹配；
• 否则：不匹配。

---

实现步骤

• 读取输入字符串 $s, t$。
• 设 $n = s$ 的长度，$m = t$ 的长度。
• 枚举所有可能的起点 $l = 0$ 到 $n - m$。
• 对每个起点，比较 $s[l..l+m-1]$ 和 $t$ 是否匹配。
  • 编写一个 check(l) 函数，判断从 $l$ 开始的长度为 $m$ 的子串是否匹配。
• 若匹配成功，输出 $(l + 1, l + m)$，注意要转换为题目要求的从 $1$ 开始的下标。

---

示范代码

#include <bits/stdc++.h>
using namespace std;
string s, t;
bool check(int l, int r)
{
    for (int i = l; i <= r; i++)
    {
        if (s[i] != t[i - l] && s[i] != '?' && t[i - l] != '?')
        {
            return 0;
        }
    }
    return 1;
}
int main()
{

    cin >> s >> t;
    int n = s.size(), m = t.size();
    for (int l = 0; l <= n - m; l++)
    {
        int r = l + m - 1;
        if (check(l, r))
        {
            cout << l + 1 << " " << r + 1 << endl;
        }
    }
    return 0;
}

---

时间复杂度分析

• 外层循环：$O(n - m + 1)$；
• 每次匹配检查：$O(m)$；
• 总时间复杂度：$O((n - m + 1) \cdot m) \leq 10^6$，在允许范围内。

---

总结

• 本题考察字符串通配符匹配的判断。
• 合理使用逐字符匹配。
• 由于数据不大，暴力匹配足以应对所有测试点。

适合练习字符串基础处理和匹配逻辑。