Codeforces 514C Watto and Mechanism 【Trie树】+【DFS】

题目大意：
输入n个单词构成单词库，然后进行m次查询，每次查询输入一个单词(注意这些单词只由a,b,c构成)，问该单词库中是否存在与当前查询的单词有且仅有一个字符不同的单词。

解题分析：
本题将单词库中所有的单词先建trie树，然后进行容错数为1的字符串匹配，主要是在trie树上跑DFS，具体步骤见代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 6e5+5;
int n,m,pos,nxt[N*3][3],num[N*3];
char s[N];

void Insert(char *s){
    int now=0;
    for(int i=0;s[i];i++){
        int to=s[i]-'a';
        if(!nxt[now][to])nxt[now][to]=++pos;
        now=nxt[now][to];
    }
    num[now]=1;
}
bool query(int now,int lc,int cur){        
    if(s[lc]=='

Codeforces 514C Watto and Mechanism 【Trie树】+【DFS】

相关推荐