机械字典匹配(Watto and Mechanism) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct TrieNode {
    int ch[3];
    bool is_end;
    TrieNode() {
        ch[0] = ch[1] = ch[2] = 0;
        is_end = false;
    }
};

vector<TrieNode> tr;

void insert_str(const string& s) {
    int u = 0;
    for (char c : s) {
        int id = c - 'a';
        if (!tr[u].ch[id]) {
            tr[u].ch[id] = (int)tr.size();
            tr.emplace_back();
        }
        u = tr[u].ch[id];
    }
    tr[u].is_end = true;
}

bool dfs_query(int u, const string& s, int pos, int diff) {
    if (pos == (int)s.size()) {
        return diff == 1 && tr[u].is_end;
    }
    int cur = s[pos] - 'a';
    for (int c = 0; c < 3; ++c) {
        int nxt = tr[u].ch[c];
        if (!nxt) continue;
        int ndiff = diff + (c != cur);
        if (ndiff <= 1) {
            if (dfs_query(nxt, s, pos + 1, ndiff)) return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    tr.reserve(600005);
    tr.emplace_back();
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        insert_str(s);
    }
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        cout << (dfs_query(0, s, 0, 0) ? "YES\n" : "NO\n");
    }
    return 0;
}