Codeforces Round #291 (Div. 2) C. Watto and Mechanism [字典树]-白红宇

Codeforces Round #291 (Div. 2) C. Watto and Mechanism [字典树]

阅读量：6123 次

发布时间：2019-06-21

本文共 3757 字，大约阅读时间需要 12 分钟。

Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: "Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position".

Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of n initial lines and m queries. He decided to entrust this job to you.

Input

The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·10⁵, 0 ≤ m ≤ 3·10⁵) — the number of the initial strings and the number of queries, respectively.

Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn't exceed 6·10⁵. Each line consists only of letters 'a', 'b', 'c'.

Output

For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).

Sample test(s)

Input

2 3 aaaaa acacaca aabaa ccacacc caaac

Output

YES NO NO

题意：n个串，m次查询，每次给一个字符串，问在原串中能不能找到一个串，与之长度相同，且只有一个字符不同。

题解：没什么好说的，字典树，强行有个数组不开成全局变量，T哭了，，，，

2015-02-15 11:39:10	GNU C++	Accepted	577 ms	99188 KB
2015-02-15 11:34:22	GNU C++	Time limit exceeded on test 32	3000 ms	101200 KB
2015-02-15 11:33:54	GNU C++	Memory limit exceeded on test 1	46 ms	262100 KB
2015-02-15 11:32:29	GNU C++	Time limit exceeded on test 32	3000 ms	90700 KB
2015-02-15 11:26:42	GNU C++	Time limit exceeded on test 32	3000 ms	89500 KB
2015-02-15 11:17:52	GNU C++	Wrong answer on test 4	15 ms	70700 KB
2015-02-15 11:14:26	GNU C++	Wrong answer on test 13	46 ms	70800 KB

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
             9 #include
             
               10 #include
              
                11 #include
               
                 12 13 #define N 300005 14 #define M 1505 15 //#define mod 10000007 16 //#define p 10000007 17 #define mod2 1000000000 18 #define ll long long 19 #define LL long long 20 #define eps 1e-6 21 //#define inf 2147483647 22 #define maxi(a,b) (a)>(b)? (a) : (b) 23 #define mini(a,b) (a)<(b)? (a) : (b) 24 25 using namespace std; 26 27 int n,m; 28 int fff[10*N]; 29 30 typedef struct 31 { 32 char v; 33 int mp[4]; 34 }PP; 35 36 int tot; 37 int cnt[10*N]; 38 39 PP p[10*N]; 40 char s[10*N]; 41 42 void insert(int l) 43 { 44 int i; 45 int now=0; 46 for(i=0;i
                
                 =2) return 0; 90 int i; 91 int ff; 92 for(i=0;i<=2;i++){ 93 if(p[now].mp[i]!=0){ 94 if(s[cou]==i+'a'){ 95 ff=check(l,cou+1,p[now].mp[i],f); 96 } 97 else{ 98 ff=check(l,cou+1,p[now].mp[i],f+1); 99 }100 if(ff==1) return 1;101 }102 }103 return 0;104 }105 106 void solve()107 {108 int i;109 int l;110 int flag;111 for(i=1;i<=m;i++){112 scanf("%s",s);113 l=strlen(s);114 // printf("l=%d\n",l);115 if(fff[l]==0){116 flag=0;117 }118 else{119 flag=check(l,0,0,0);120 }121 if(flag==1){122 printf("YES\n");123 }124 else{125 printf("NO\n");126 }127 }128 }129 130 void out()131 {132 133 }134 135 int main()136 {137 //freopen("data.in","r",stdin);138 //freopen("data.out","w",stdout);139 //scanf("%d",&T);140 //for(int ccnt=1;ccnt<=T;ccnt++)141 //while(T--)142 //scanf("%d%d",&n,&m);143 while(scanf("%d%d",&n,&m)!=EOF)144 {145 ini();146 solve();147 out();148 }149 return 0;150 }

转载于:https://www.cnblogs.com/njczy2010/p/4293135.html

你可能感兴趣的文章