带有问号通配符的字符串模式匹配

问题

给定原串 $s$ 与模式串 $t$。其中模式串可能含有一些 ? 字符（而原串没有），问号可以与任何字符匹配。问模式串与 $s$ 中哪些位置匹配？

形式化的：

我们称两个字符串相等，当且仅当：

它们长度相等
对于任意一个位置 $i$（$0 \leq i < \mathrm{len}$，$\mathrm{len}$ 是两个字符串的长度），两个字符串在这个位置上的对应字符相等，或至少一个字符串在这个位置上的对应字符是问号。

现在的问题是，求出所有的 $0 \leq i \leq \operatorname{len}(s) - \operatorname{len}(t)$ 满足 $s$ 从 $i$ 开始（包含 $i$），长度为 $\operatorname{len}(t)$ 的子串与 $t$ 相等。

下设 $n := \operatorname{len}(s), \; m := \operatorname{len}(t)$。

bitset 做法

bitset 能够简单高效的解决这个问题，复杂度为 $O(nm/w)$。

具体的：对于每种字符 $c$，我们维护一个长度为 $n$ 的 bitset。bitset 的下标为 $i$ 的位置为 true 当且仅当 $s_i = c$。

注意到，假如 $i$ 是一个匹配的起始点，这意味着 $s_{i+j} = t_j$ 对所有 $0 \leq j < m$ 的 $j$ 成立。反过来：

一个匹配的起始点 $i$，必须在一个 $s_k = t_j$ 的位置 $k$ 前面 $j$ 格。

我们就可以遍历 $t$ 中所有字符，然后找到当前遍历到的字符在 $s$ 中的所有出现位置，它们向前平移 $j$（设 $j$ 是当前遍历到的下标）就是所有可能的匹配位置。那么我们用 bitset 的右移和逻辑与处理就行了。

通配符怎么办？通配符毫无约束效力，直接什么都不做就是对的。

简单的示例代码：

 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
#include <bits/stdc++.h>

using namespace std;
basic_string<char> s, t;
array<bitset<100000>, 26> pos;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s >> t;
    for (int i = 0; i < s.size(); ++i) {
        pos[s[i] - 'a'][i] = true;
    }

    bitset<100000> ans;
    for (int i = 0; i <= s.size() - t.size(); ++i) {
        ans[i] = true;
    }

    for (int i = 0; i < t.size(); ++i) {
        if (t[i] != '?') {
            ans &= (pos[t[i] - 'a'] >> i);
        }
    }

    vector<int> tmp;
    for (int i = ans._Find_first(); i < s.size(); i = ans._Find_next(i)) {
        tmp.push_back(i);
    }

    cout << tmp.size() << '\n';
    for (int i: tmp) {
        cout << i << '\n';
    }
    return 0;
}

巨大字符集

假如字符集不再是小写字母，而可能是任意整数，怎么做呢？

其实很简单。首先离散化所有字符。

然后还是照搬套路，但这次我们不再按位置枚举，而是按 $t$ 中不同的字符种类枚举，对于每种字符，我们遍历一次 $s$，构建出现位置的 bitset，并遍历它在 $t$ 中出现的每个位置，分别进行对应的移位和与即可。

时间复杂度不变。空间复杂度线性。

FFT/NTT

也可以解决本题，复杂度是更优秀的 $O(n \log n)$，但是太难了，不讲。

问题#

bitset 做法#

巨大字符集#

FFT/NTT#

问题

bitset 做法

巨大字符集

FFT/NTT