Untitled

mail@pastecode.io avatar
unknown
plain_text
24 days ago
2.3 kB
2
Indexable
Never
#include <iostream>
#include <deque>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <numeric>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <string>
#include <array>
#include <cstdlib>
#include <unordered_map>
//#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define ld double
#define fr first;
#define sc second;
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const ll N = 2 * 1e5 + 5, inf = 1e15;
const ll mod = 1e9 + 7;
 
struct Node
{
    ll ch[3];
    ll sz = 0, ends = 0;
    ll& operator[](char x) { return ch[x]; }
};
 
class Trie
{
public:
    vector<Node> trie;
    ll newNode()
    {
        trie.emplace_back();
        return trie.size() - 1;
    }
    void init()
    {
        trie.clear();
        newNode();
    }
    void update(string& s, ll op)
    {
        ll u = 0;
        for (char& i : s)
        {
            ll ch = i;
            ch -= 97;
            if (!trie[u][ch])
                trie[u][ch] = newNode();
            u = trie[u][ch];
            trie[u].sz += op;
        }
        trie[u].ends += op;
    }
    bool query(string& s, ll u, ll i, bool dif)
    {
        if (i == s.size()) return trie[u].ends;
        bool ans = 0;
        if (!dif)
        {
            for (ll j = 0; j < 3; j++)
            {
                ll v = trie[u][j];
                if (!trie[v].sz) continue;
                bool df = (s[i] - 97 != j);
                ans |= query(s, v, i + 1, df);
            }
        }
        else
        {
            ll v = trie[u][s[i]-97];
            if (!trie[v].sz) return false;
            ans |= query(s, v, i + 1, dif);
        }
        return ans;
    }
};
 
void solve(ll t)
{
    ll n, m;
    cin >> n >> m;
    Trie trie;
    trie.init();
    while (n--)
    {
        string s;
        cin >> s;
        trie.update(s, 1);
    }
    while (m--)
    {
        string s; cin >> s;
        if (trie.query(s, 0, 0, 0))
            cout << "YES\n";
        else cout << "NO\n";
    }
}
 
int main()
{
    FIO;
    ll t = 1;
    //cin>>t;
    for (ll i = 1; i <= t; i++)
    {
        solve(i);
    }
}
Leave a Comment