C. Watto and Mechanism(字典树添dfs)

C. Watto and Mechanism(字典树加dfs)

CF的传送门

题目的意思是给你n个字符串和m个询问,每次询问一个字符串是否可以通过改变其中的一个字母来得到n个字符串中

的任意一个,如果可以输出"YES",否则输出"NO";

字典树加DFS,首先对所给的字符串建立一颗字典树,然后对于每一个字符串的查询,进行dfs就行,具体看下代码吧!

在这里介绍个讲得不错的字典树博客: http://www.cnblogs.com/tanky_woo/archive/2010/09/24/1833717.html#3034715

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#include <algorithm>

#define ls u << 1
#define rs u << 1 | 1
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define INF 0x3f3f3f3f
#define MAX 3

using namespace std;
typedef long long ll;
const int M = 6e5 + 100;
const int mod = 2147483647;
char s[M];

struct Trie {
    int index; //根据需要进行变化
    Trie *next[MAX]; //表示每一层包含有多少种类的数
    Trie() { //初始化
        index = -1;
        memset(next,0,sizeof(next));
    }
};

Trie *root = new Trie; //字典树的根

void Trie_insert(Trie *tr,int len) { //递归建立字典树
    if(s[len]) {
        int u = s[len] - 'a';
        if(tr -> next[u] == 0)
            tr -> next[u] = new Trie;
        Trie_insert(tr -> next[u],len + 1);
    } else tr->index = 1; //标记为1表示以到达字符串结尾
}

/*int deal_Trie(Trie *tr){ //递归销毁字典树
    if(tr == NULL){
        return 0;
    }
    for(int i = 0; i < MAX; i++){
        if(tr -> next[i]) //如果下一层还有,则递归销毁
            deal_Trie(tr -> next[i]);
    }
    free(tr);
    return 0;
}*/

bool dfs(Trie *tr,int len,int num) {
    if(s[len]) {
        int u = s[len] - 'a';
        if(tr->next[u] != 0) {
            if(dfs(tr->next[u],len + 1,num)) return true;
        }
        if(!num) {
            for(int i = 0; i < MAX; i++) {
                if(i != u && tr->next[i] != 0) {
                    if(dfs(tr->next[i],len + 1,num + 1)) return true;
                }
            }
        }
    } else {
        if(num && tr->index == 1) return true;
    }
    return false;
}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    while(n--) {
        scanf("%s",s);
        Trie_insert(root,0);
    }
    while(m--) {
        scanf("%s",s);
        if(dfs(root,0,0)) puts("YES");
        else puts("NO");
    }
    return 0;
}

1楼ACMWONDER昨天 16:37: So diao !!!

C. Watto and Mechanism(字典树添dfs)

相关推荐