fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int trie[600005][4], k, g;
  6. char s[600005], temp[600005];
  7. bool ans;
  8.  
  9. void insert(){
  10.     int index, node;
  11.     node = 0;
  12.     for(int i=0 ; s[i] ; i++){
  13.         index = s[i] - 'a';
  14.         if(trie[node][index] == -1){
  15.             trie[node][index] = k++;
  16.         } 
  17.         node = trie[node][index];
  18.     }
  19.  
  20.     trie[node][3] = 1;
  21. }
  22.  
  23. void  search(int i, int x, int node, int len){
  24.     int index;
  25.     g++;
  26.     index = s[i] - 'a';
  27.     if(i == len){
  28.         if(trie[node][3] == 1 && x==1)
  29.             ans = true;
  30.         return;
  31.     } 
  32.  
  33.     if(ans)
  34.         return;
  35.  
  36.     if(x == 1){
  37.     	if(trie[node][index] != -1)
  38.        		search(i+1, 1, trie[node][index], len);
  39.     } else if(x == 0) {
  40.     	if(trie[node][index] != -1)
  41.     		search(i+1, 0, trie[node][index], len);
  42.     	if(ans)
  43.     		return;
  44.         for(int j=0 ; j<3 ; j++){
  45.             if(index != j){
  46.             	if(trie[node][j] != -1)
  47.                	 search(i+1, 1, trie[node][j], len);
  48.             }
  49.             if(ans)
  50.             	return;
  51.         }
  52.     }
  53. }
  54.  
  55. int main(){
  56.     int n, m, l, index, flag;
  57.     cin>>n>>m;
  58.  
  59.     k = 1;
  60.     for(int i=0 ; i<600005 ; i++){
  61.         for(int j=0 ; j<3 ; j++){
  62.             trie[i][j] = -1;
  63.         }
  64.     }
  65.  
  66.     getchar();
  67.     for(int i=0 ; i<n ; i++){
  68.         scanf("%[^\n]s", s);
  69.         getchar();
  70.         insert();
  71.     }
  72.  
  73.     for(int i=0 ; i<m ; i++){
  74.         scanf("%[^\n]s", s);
  75.         getchar();
  76.         l = strlen(s);
  77.         ans = false;
  78.  
  79.         search(0, 0, 0, l);
  80.  
  81.         if(ans){
  82.             printf("YES\n");
  83.         } else {
  84.             printf("NO\n");
  85.         }
  86.     }
  87.  
  88. 	cout<<g<<endl;
  89.     return 0;
  90. }
Success #stdin #stdout 0s 13648KB
comments (?)
stdin
copy 
9 9
caccbcacabccba
aacbcbcaabacbcbcba
babccaaacccacbb
caaabcaacbababbabbb
abbaccacabacaaaa
bccbccababcaacb
caacbcaacbababbabbb
bcacababbbcaaca
ccbbcbababbccaab
bbcbccababcaacb
aacccbabbacbabacaca
bbcbcccbabcaacb
acbacacbcacc
caaabcaaabacabbabbb
abbbabaaaba
aacccbcaabacbcbcba
abbaccacabbcaaaa
aaccbbcabbacbcbcba
stdout
copy 
YES
NO
NO
NO
NO
NO
YES
YES
NO
134
https://ideone.com/uNbDf9
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!