Untitled
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