NC19873. [AHOI2005]VIRUS 病毒检测
描述
输入描述
第一行有一个字符串，由A、C、T、G、*、? 组成。表示“病毒模版片段”。“病毒模版片段”的长度不超过1000。
第二行有一个整数N（0 < N < 500），表示机器人搜集到的RNA片段的数目。随后的N行，每一行有一个字符串，由A、C、T、G组成，表示一个RNA片段。每个RNA片段的长度不超过500。
注意：“病毒模版片段”和RNA片段的长度都至少为1。
输出描述
只有一行输出，为整数M，即不是病毒的RNA片段的数目。
示例1
输入:
A*G?C 3 AGTC AGTGTC AGTGC
输出:
1
C++(g++ 7.5.0) 解法, 执行用时: 367ms, 内存消耗: 145480K, 提交时间: 2022-10-26 22:15:32
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list>
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
using namespace std;
const LL MOD=100003;
const int N=510,INF=1e9;
string s0,s;
int cnt,tr[N*N][26],idx,num[N*N];
bool st[N*N][1010];
map<char,int>mp;
void ins()
{
int p=0;
rep(i,0,s.size()){
if(!tr[p][mp[s[i]]]) tr[p][mp[s[i]]]=++idx;
p=tr[p][mp[s[i]]];
}
++num[p];
}
void dfs(int u,int nw)
{
if(nw==s0.size()){
cnt+=num[u];
num[u]=0;
return;
}
if(st[u][nw]) return;
st[u][nw]=1;
if(s0[nw]=='?'){
if(tr[u][mp['A']]) dfs(tr[u][mp['A']],nw+1);
if(tr[u][mp['C']]) dfs(tr[u][mp['C']],nw+1);
if(tr[u][mp['T']]) dfs(tr[u][mp['T']],nw+1);
if(tr[u][mp['G']]) dfs(tr[u][mp['G']],nw+1);
}
else if(s0[nw]=='*'){
dfs(u,nw+1);
if(tr[u][mp['A']]) dfs(tr[u][mp['A']],nw+1),dfs(tr[u][mp['A']],nw);
if(tr[u][mp['C']]) dfs(tr[u][mp['C']],nw+1),dfs(tr[u][mp['C']],nw);
if(tr[u][mp['T']]) dfs(tr[u][mp['T']],nw+1),dfs(tr[u][mp['T']],nw);
if(tr[u][mp['G']]) dfs(tr[u][mp['G']],nw+1),dfs(tr[u][mp['G']],nw);
}
else{
if(tr[u][mp[s0[nw]]]) dfs(tr[u][mp[s0[nw]]],nw+1);
}
}
void solve()
{
mp['A']=0,mp['C']=1,mp['T']=2,mp['G']=3;
cin>>s0;
int n;
cin>>n;
rep(i,0,n) cin>>s,ins();
dfs(0,0);
cout<<n-cnt;
}
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("title.in","r",stdin);
// freopen("title.out","w",stdout);
// #endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
//cin>>_;
while(_--){
solve();
}
// rep(i,1,_+1){
// cout<<"Case "<<i<<": ";
// solve();
// }
return 0;
}
C++14(g++5.4) 解法, 执行用时: 177ms, 内存消耗: 66768K, 提交时间: 2019-11-24 15:24:43
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXNODE = 5e5+5;
const int MAXN = 1e3+5;
inline int read(){
char ch = getchar();
int x = 0;
while(ch<'0'||ch>'9') ch = getchar();
while(ch>='0' && ch<='9') x = (x<<3)+(x<<1)+ch-48,ch = getchar();
return x;
}
struct Trie{
int nxt[MAXNODE][4],cnt[MAXNODE];
char T[MAXN],S[MAXN];
int sz,n,ans,length;
bitset<MAXN> dp[MAXNODE];
int idx(char ch){
if(ch=='A') return 0;
else if(ch=='C') return 1;
else if(ch=='G') return 2;
else return 3;
}
void Read(){
scanf("%s",T);
length = strlen(T);
n = read();
for(int i=1;i<=n;i++) scanf("%s",S),Insert(S);
dfs(0,0);
printf("%d\n",n-ans);
}
void Insert(char *s){
int len=strlen(s),root=0;
for(int i=0;i<len;i++){
if(!nxt[root][idx(s[i])]) nxt[root][idx(s[i])] = ++sz;
root = nxt[root][idx(s[i])];
}
cnt[root]++;
}
void dfs(int root,int now){
if(now==length) { ans+=cnt[root],cnt[root]=0;return; }
if(dp[root][now]) return;
dp[root][now]=1;
if(T[now]>='A' && T[now]<='Z'){
if(nxt[root][idx(T[now])])
dfs(nxt[root][idx(T[now])],now+1);
return;
}
if(T[now]=='?'){
for(int i=0;i<4;i++)
if(nxt[root][i])
dfs(nxt[root][i],now+1);
return;
}
if(T[now]=='*'){
dfs(root,now+1);
for(int i=0;i<4;i++)
if(nxt[root][i])
dfs(nxt[root][i],now+1),dfs(nxt[root][i],now);
return;
}
}
}Automaton;
int main(){
Automaton.Read();
}
C++(clang++11) 解法, 执行用时: 118ms, 内存消耗: 888K, 提交时间: 2021-02-14 10:54:19
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int Maxn=510;
bool f[Maxn*2][Maxn];
int l,len,c[Maxn*2];
char str[Maxn*2],s[Maxn];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int main()
{
scanf("%s",str+1);
int T=read(),ans=T;
l=strlen(str+1);
while(T--)
{
memset(c,63,sizeof(c));
memset(f,false,sizeof(f));
scanf("%s",s+1);
len=strlen(s+1);
f[0][0]=true;
for(int i=1;i<=l;i++)
{
if(str[i]!='*')
{
for(int j=1;j<=len;j++)
if(str[i]=='?'||str[i]==s[j])
{
f[i][j]|=f[i-1][j-1];
if(str[i-1]=='*'&&c[i-1]<j)
f[i][j]|=1;
}
}
else
{
if(i==1)
f[1][0]=true;
for(int j=1;j<=len;j++)
{
f[i][j]=(f[i-1][j]|f[i][j-1]);
if(f[i][j])
c[i]=min(c[i],j);
}
}
}
if(f[l][len])
ans--;
}
printf("%d",ans);
}