Problem - 514C - Codeforces
题意：
思路：
其实是trie上dfs的板题
先把字符串插入到字典树中
对于每次询问，都去字典树上dfs
注意到字符集只有3，因此如果发现有不同的字符，去枚举新的字符文章来源：https://www.toymoban.com/news/detail-626124.html
Code：文章来源地址https://www.toymoban.com/news/detail-626124.html
#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;
}到了这里，关于【枚举+trie+dfs】CF514 C的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
