【枚举+trie+dfs】CF514 C

Problem - 514C - Codeforces

题意：

 

思路：

其实是trie上dfs的板题

先把字符串插入到字典树中

对于每次询问，都去字典树上dfs

注意到字符集只有3，因此如果发现有不同的字符，去枚举新的字符

Code：

#include <bits/stdc++.h>using i64 = long long;using namespace std;const int N = 4e5 + 10;
const int M = 3e6 + 10;
const int P = 131;string s;int tot = 0;
int tag[N];
int tr[N][30];void insert(string x) {int p = 0;for (int i = 0; i < x.size(); i ++) {int u = x[i] - 'a';if (! tr[p][u]) {tr[p][u] = ++tot;}p = tr[p][u];}tag[p] = 1;
}
bool dfs(int dep, int u, int num) {if (s[dep]) {int v = s[dep] - 'a';if (tr[u][v]) {if (dfs(dep + 1, tr[u][v], num)) return true;}if (!num) {for (int j = 0; j < 3; j ++) {if (j != v && tr[u][j]) {if (dfs(dep + 1, tr[u][j], num + 1)) return true;}}}}else if (tag[u] && num) return true;return false;
}
void solve() {int n,m;cin >> n >> m;for (int i = 1; i <= n; i ++) {cin >> s;insert(s);}for (int i = 1; i <= m; i ++) {cin >> s;if (dfs(0, 0, 0)) {cout << "YES" << "\n";}else {cout << "NO" << "\n";}}
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;//cin >> t;while(t --) {solve();}return 0;
}