tries树第一题 codeforces 514C - Watto and Mechanism

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int Max=6*1e5+10;
char str[Max];
int val[Max],ch[Max][3];
int sz;//节点总数
void Insert()
{
    int u=0,n=strlen(str);
    for(int i=0;i<n;i++){
        int c=str[i]-‘a‘;
        if(!ch[u][c]){                   //节点不存在
            memset(ch[sz],0,sizeof(ch[sz]));
            val[sz]=0;                   //上一节点现在不是单词节点了
            ch[u][c]=sz++;               //新建节点
        }
        u=ch[u][c];                      //往下走
    }
    val[u]=1;                           //本节点是单词节点
}
bool dfs(int rt,int p,int d,int len)
{
    if(d>1){
        return false;
    }
    if(p==len){
        if(d==1 && val[rt] ){
            return true;
        }
        else{
            return false;
        }
    }
    for(int i=0;i<3;i++){
        if(ch[rt][i]){               //子节点存在
            if(dfs(ch[rt][i],p+1,d+(i!=str[p]-‘a‘),len)){
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&a,&b)){
        memset(val,0,sizeof(val));
        memset(ch,0,sizeof(ch));
        sz=1;
        for(int i=0;i<a;i++){
            scanf("%s",str);
            //puts(str);
            Insert();
        }
        for(int i=0;i<b;i++){
            scanf("%s",str);
            //puts(str);
            if(dfs(0,0,0,strlen(str))){
                printf("YES\n");
            }
            else{
                printf("NO\n");
            }
        }
    }
    return 0;
}