색상은 trie에 insert, 닉네임은 unordered_set에 insert.
그리고 쿼리 앞부분부터 트라이에서 찾는다. 트라이에 알파벳이 존재하지 않으면 return false, 트라이에 해당 색상이 존재하고, 뒷쪽 substring이 unordered_set에 존재하면 return true, 끝까지 다 돌았는데도 못찾으면 return false.
#include <bits/stdc++.h>
using namespace std;
unordered_set<string> team;
struct Trie {
Trie* t[26];
bool end;
Trie() {
memset(t, 0, sizeof(t));
end = false;
}
~Trie() {
for (int i = 0; i < 26; i++) {
if (t[i]) delete t[i];
}
}
void insert(string& s, int idx) {
if (idx == s.length()) {
end = true;
return;
}
if (!t[s[idx]-'a']) {
t[s[idx]-'a'] = new Trie();
}
t[s[idx]-'a']->insert(s, idx+1);
}
bool solve(string& s, int idx) {
if (idx == s.length()) return false;
if (!t[s[idx]-'a']) return false;
if (t[s[idx]-'a']->end && team.find(s.substr(idx+1)) != team.end()) return true;
return t[s[idx]-'a']->solve(s, idx+1);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Trie root;
int c, n, q;
cin >> c >> n;
while (c--) {
string s;
cin >> s;
root.insert(s, 0);
}
while (n--) {
string s;
cin >> s;
team.insert(s);
}
cin >> q;
while (q--) {
string s;
cin >> s;
if (root.solve(s, 0)) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
정답률 단 14% 1트 성공..!