80分 记忆化搜索 + trie树 求找错
查看原帖
80分 记忆化搜索 + trie树 求找错
44072
dyzxjzx楼主2023/11/27 20:26

第三个点和第八个点错

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int son[1010][7], n, idx, lasts, dp[510][510];
int op(char x)
{
	if (x == 'A') return 1;
	if (x == 'C') return 2;
	if (x == 'T') return 3;
	if (x == 'G') return 4;
	if (x == '*') return 5;
	if (x == '?') return 6;
}
void insert(string s)
{
	int p = 0;
	for (int i = 0; i < s.size(); i++)
	{
		int u = op(s[i]);
		if ( !son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}
	lasts = p;
	return ;
}
bool query(string s, int t, int p)
{
	if (dp[t][p] != -1) return dp[t][p];
	if (t == s.size() && p == lasts ) return true;
	if (t == s.size() || p == lasts ) return false;
	int u = op(s[t]);
	bool flag = false;
	if (son[p][u])
		if ( query(s, t + 1, son[p][u]) )
			flag = true;
	if (son[p][5])
		if ( query(s, t + 1, p) || query(s, t, son[p][5]) || query(s, t + 1, son[p][5]) )
			flag = true;
	if (son[p][6])
		if ( query(s, t + 1, son[p][6]) )
			flag = true;
	dp[t][p] = flag;
	return flag;
}
int main()
{
	string s;
	cin>>s>>n;
	insert(s);
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		memset(dp, -1, sizeof(dp));
		string x;
		cin>>x;
		if(  query(x, 0, 0) )
			ans ++;
	}
	cout<<n - ans<<endl;
 } 
2023/11/27 20:26
加载中...