Codeforces 514C Watto and Mechanism（字典树）

题目链接 Watto and Mechanism

题意给出$n$个串（相当于字典），然后给出$m$个询问。

每个询问以字符串的形式给出，你需要改变这个字符串中的任意一个字符

（必须改变且只能改变一个）

如果改变之后可以成为$n$个串中的一个字符串，则输出$YES$，否则输出$NO$。

字母集合为$\left\{ a, b, c \right\}$

考虑字典树。

首先把$n$个单词插入字典树中。

询问的时候用$dfs$，$flag$表示搜索到当前是否已经改变过一个字符。

如果已经改变过那只能按照当前剩下的字符串一条路查询下去。

否则可以按老字符或新字符进行查询。

（这题很卡内存）

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 2e7 + 3;

char s[600010];

int n, q, ans, len, tot = 0;

int ch[N][3];

bitset <N> cnt;

int newnode(){

	++tot;

	rep(i, 0, 2) ch[tot][i] = 0;

	cnt[tot] = 0;

	return tot;

}

void insert(char* s){

	int now = 0;

	for (int i = 0; s[i]; ++i){

		int w = s[i] - 'a';

		if (!ch[now][w]) ch[now][w] = newnode();

		now = ch[now][w];

	}

	cnt[now] = 1;

}

void dfs(int x, int flag, int now){

	if (ans) return;

	if (x == len && flag && cnt[now]){ ans = 1; return;}

	if (x >= len) return;

	if (flag){

		int w = s[x] - 'a';

		if (ch[now][w]) dfs(x + 1, flag, ch[now][w]);

	}

	else{

		rep(i, 0, 2)

			if (i != s[x] - 'a' && x + 1 == len && ch[now][i] && cnt[ch[now][i]]) ans = 1;

		rep(i, 0, 2) if (i != s[x] - 'a' && ch[now][i]){

			dfs(x + 1, 1, ch[now][i]);

		}

		int w = s[x] - 'a';

		if (ch[now][w]){

			dfs(x + 1, flag, ch[now][w]);

		}

	}

}

int main(){

	scanf("%d%d", &n, &q);

	rep(i, 1, n){

		scanf("%s", s);

		insert(s);

	}

	rep(i, 1, q){

		scanf("%s", s);

		len = strlen(s);

		ans = 0;

		dfs(0, 0, 0);

		puts(ans ? "YES" : "NO");

	}

	return 0;

}

巴特西

Codeforces 514C Watto and Mechanism（字典树）

最新文章

热门文章