枚举+trie+dfsCF514 C

Problem - 514C - Codeforces

题意：

思路：

其实是trie上dfs的板题

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

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

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

Code：

1.  
   #include <bits/stdc .h>
2.  
    
3.  
   using i64 = long long;
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 4e5 10;
8.  
   const int M = 3e6 10;
9.  
   const int P = 131;
10.  
     
11.  
    string s;
12.  
     
13.  
    int tot = 0;
14.  
    int tag[N];
15.  
    int tr[N][30];
16.  
     
17.  
    void insert(string x) {
18.  
    int p = 0;
19.  
    for (int i = 0; i < x.size(); i ) {
20.  
    int u = x[i] - 'a';
21.  
    if (! tr[p][u]) {
22.  
    tr[p][u] = tot;
23.  
    }
24.  
    p = tr[p][u];
25.  
    }
26.  
    tag[p] = 1;
27.  
    }
28.  
    bool dfs(int dep, int u, int num) {
29.  
    if (s[dep]) {
30.  
    int v = s[dep] - 'a';
31.  
    if (tr[u][v]) {
32.  
    if (dfs(dep 1, tr[u][v], num)) return true;
33.  
    }
34.  
    if (!num) {
35.  
    for (int j = 0; j < 3; j ) {
36.  
    if (j != v && tr[u][j]) {
37.  
    if (dfs(dep 1, tr[u][j], num 1)) return true;
38.  
    }
39.  
    }
40.  
    }
41.  
    }
42.  
    else if (tag[u] && num) return true;
43.  
    return false;
44.  
    }
45.  
    void solve() {
46.  
    int n,m;
47.  
    cin >> n >> m;
48.  
     
49.  
    for (int i = 1; i <= n; i ) {
50.  
    cin >> s;
51.  
    insert(s);
52.  
    }
53.  
     
54.  
    for (int i = 1; i <= m; i ) {
55.  
    cin >> s;
56.  
    if (dfs(0, 0, 0)) {
57.  
    cout << "YES" << "\n";
58.  
    }else {
59.  
    cout << "NO" << "\n";
60.  
    }
61.  
    }
62.  
    }
63.  
    signed main(){
64.  
    ios::sync_with_stdio(false);
65.  
    cin.tie(nullptr);
66.  
     
67.  
    int t = 1;
68.  
    //cin >> t;
69.  
    while(t --) {
70.  
    solve();
71.  
    }
72.  
    return 0;
73.  
    }

这篇好文章是转载于：学新通技术网