Test19 MLE求调
查看原帖
Test19 MLE求调
702147
Jason20090916楼主2024/8/19 20:45
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fileO(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fileC fclose(stdin); fclose(stdout);
using namespace std;

inline ll read(){
	ll f=1,outt=0;char a=getchar();
	while(a>'9'||a<'0'){if(a=='-')f=-1;a=getchar();}
	while(a<='9'&&a>='0'){outt*=10;outt+=a-'0';a=getchar();}
	return f*outt;
}

const int MAXN = 5e6 + 9;

int n, m;
int trie[MAXN][3];
int ed[MAXN];

int change(char c)
{
	return c - 'a';
}

int root = 1;
int cnt = 1;
void add(string s)
{
	int nown = root;
	for(auto i : s)
	{
		int k = change(i);
		if(!trie[nown][k])
		{
			trie[nown][k] = ++cnt;
		}
		nown = trie[nown][k];
		ed[nown]++;
	}
}

bool dfs(string s, int i, int nown, int flag)
{
	if(flag > 1)
	return 0;
	if(i == (int)s.length())
	return (flag == 1) && ed[nown];
	int k = change(s[i]);
	bool fg = 0;
	if(trie[nown][k])
	{
		fg = fg || dfs(s, i + 1, trie[nown][k], flag);
	}
	if(trie[nown][(k + 1) % 3])
	{
		fg = fg || dfs(s, i + 1, trie[nown][(k + 1) % 3], flag + 1);
	}
	if(trie[nown][(k + 2) % 3])
	{
		fg = fg || dfs(s, i + 1, trie[nown][(k + 2) % 3], flag + 1);
	}
	return fg;
}

void solve()
{
	n = read();
	m = read();
	for(int i = 0; i < n; i++)
	{
		string ins;
		cin >> ins;
		add(ins);
	}
	while(m--)
	{
		string fs;
		cin >> fs;
		if(dfs(fs, 0, root, 0))
		{
			cout << "YES\n";
		}
		else
		{
			cout << "NO\n";
		}
	}
	return;
}

int T;
int main()
{
	T = 1;
//	T = read();
	while(T--)
	{
		solve();
	}
 	return 0;
}

2024/8/19 20:45
加载中...