解题思路

我们通过字典树（Trie）和深度优先搜索（DFS）来解决模式匹配的问题。字典树的每个节点代表一个字符或通配符（? 和 *），通过深度优先搜索遍历匹配模式。

1. 数据结构设计

• 字典树：我们构造一颗字典树，树的每个节点表示一个字符。如果模式中包含通配符 ? 和 *，则我们将它们看作字母 a-z 后的特殊字符：
  • ? 对应第26个字符（编号 26）。
  • * 对应第27个字符（编号 27）。
• tree[root][id]：表示在 root 节点下存在的第 id 个孩子节点（id 取值为 0-25，26 对应 *，27 对应 ?）。
• p[i]：记录第 i 个字符串的尾结点编号，即该字符串在字典树中的最后一个字符所在的节点。
• flag[root]：如果 flag[root] 为 true，表示 root 节点是某个字符串的结束节点。

2. 模式匹配过程

• add 函数：用于将模式添加到字典树中。在插入模式时，如果字符是字母，则通过字符的 ASCII 值计算出编号；如果是 ? 或 *，则分别赋予编号 26 和 27。
• find 函数：使用 DFS 来尝试从字典树的根节点开始匹配每个字符：
  • 如果字符是字母，则进入对应的子节点。
  • 如果字符是 ?，匹配任何单个字符，跳到下一个字符。
  • 如果字符是 *，匹配零个或多个字符，可能跳到任意位置。
  • 在匹配过程中，我们使用 vis 数组记录某个节点是否已经匹配成功。

3. 特殊处理

• *：可以匹配任意长度的字符，* 后面可以匹配零个或多个字符，因此在 DFS 中我们会遍历从当前位置开始的所有可能的匹配。
• ?：只能匹配一个字符，所以 DFS 时每次遇到 ? 都要跳到下一个字符。

4. 输出匹配结果

• 对于每个查询单词，我们通过调用 find 函数进行匹配。如果某个单词与多个模式匹配，输出匹配的模式编号；否则输出 "Not match"。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 2e6 + 10;
int tree[maxn][30];  // 0-25: a-z, 26: '*', 27: '?'
int tot = 0;
int sum[maxn];
bool flag[maxn];
int n, q;
int vis[maxn];
int p[10010];  // p[i] 存储第i个模式串对应的末尾节点
char s[10010];

// 插入模式串到 Trie
void add(char *s, int idx) {
    int root = 0;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        int id;
        if (s[i] == '*') id = 26;
        else if (s[i] == '?') id = 27;
        else id = s[i] - 'a';

        if (!tree[root][id]) tree[root][id] = ++tot;
        root = tree[root][id];
        sum[root]++;
    }
    p[idx] = root;
    flag[root] = true;
}

// 匹配查询串 s，从 trie 节点 num 开始，s[pos] 是当前字符
void find(char *s, int num, int pos) {
    int len = strlen(s);

    // 如果已经匹配完整，检查是否为某个模式串终点
    if (pos == len && flag[num]) {
        vis[num] = 1;
    }

    // 匹配 '*': 可以匹配0个或多个字符
    if (tree[num][26]) {
        for (int i = pos; i <= len; i++) {
            find(s, tree[num][26], i);
        }
    }

    // 匹配 '?': 仅能匹配一个字符
    if (tree[num][27] && pos < len) {
        find(s, tree[num][27], pos + 1);
    }

    // 匹配普通字符
    if (pos < len && s[pos] >= 'a' && s[pos] <= 'z') {
        int id = s[pos] - 'a';
        if (tree[num][id]) {
            find(s, tree[num][id], pos + 1);
        }
    }
}

int main() {
    scanf("%d%d", &n, &q);

    // 初始化全局变量（防止 Trie 污染）
    memset(tree, 0, sizeof(tree));
    memset(sum, 0, sizeof(sum));
    memset(flag, 0, sizeof(flag));
    memset(p, 0, sizeof(p));
    tot = 0;

    // 构建 Trie 树
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        add(s, i);
    }

    // 查询每个输入串是否能匹配到模式
    for (int i = 0; i < q; i++) {
        memset(vis, 0, sizeof(vis));
        scanf("%s", s);
        find(s, 0, 0);

        bool found = false;
        for (int j = 0; j < n; j++) {
            if (vis[p[j]]) {
                printf("%d ", j);
                found = true;
            }
        }
        if (!found) puts("Not match");
        else printf("\n");
    }

    return 0;
}

代码解释

1. add 函数：将每个模式添加到字典树中。通过遍历模式字符串中的每个字符，更新字典树的节点。如果是字母，则按其 ASCII 值计算编号；如果是 ? 或 *，则分别赋予特殊编号。

2. find 函数：深度优先搜索（DFS）函数，从字典树的某个节点开始匹配查询单词。如果遇到 *，递归尝试匹配零个或多个字符；如果遇到 ?，则跳到下一个字符；如果是普通字母，则继续匹配下一个字符。

3. 主函数：首先读取模式和查询单词，使用 add 函数将模式添加到字典树中。然后，对于每个查询单词，调用 find 函数检查它是否与某个模式匹配。如果匹配，则输出模式编号，否则输出 "Not match"。

时间复杂度分析

• add 函数：每个模式的添加时间复杂度是 $O(L)$，其中 $L$ 是模式的长度。由于每个模式的长度最多为 6，添加操作的时间复杂度是常数级别。
• find 函数：每次查询单词的匹配操作时间复杂度为 $O(L \times K)$，其中 $L$ 是查询单词的长度，$K$ 是字典树的节点数（最多为 $2 \times 10^6$）。
• 总体时间复杂度：对于每个查询单词，匹配操作的时间复杂度是 $O(L \times K)$，因此对于 $q$ 个查询单词，最终的时间复杂度为 $O(q \times L \times K)$。

总结

通过字典树和深度优先搜索，我们高效地解决了这个模式匹配问题。字典树保证了模式的高效存储和查找，而深度优先搜索处理了复杂的模式匹配规则。