zcmimi's blog
avatar
zc
2020-10-13 21:01:06
  • 本文总阅读量

查看原题

点击跳转

首先将所有RNA序列插入trie

然后用病毒模版片段trie上搜索

对于?,可以匹配任意一种

对于*,可以选择

  1. 不匹配,*当作没有
  2. 匹配,下一个停止用*匹配
  3. 匹配,下一个继续用*匹配
#include<bits/stdc++.h>
const int N=1011,M=500011;
int n,len,cnt,c[M][4],end[M],ans;
char s[N],t[N];
int id(char c){
    if(c=='A')return 0;
    if(c=='C')return 1;
    if(c=='T')return 2;
    if(c=='G')return 3;
    return -1;
}
void ins(char*s){
    int p=0;
    for(int i=0;~id(s[i]);++i){
        if(!c[p][id(s[i])])c[p][id(s[i])]=++cnt;
        p=c[p][id(s[i])];
    }
    ++end[p];
}
std::bitset<N>v[M];
void dfs(int p,int d){
    if(d==len){
        ans-=end[p];end[p]=0;
        return;
    }
    if(v[p][d])return;v[p][d]=1;
    if(~id(s[d])){
        if(c[p][id(s[d])])dfs(c[p][id(s[d])],d+1);
        return;
    }
    if(s[d]=='?'){
        for(int i=0;i<4;++i)
            if(c[p][i])dfs(c[p][i],d+1);
        return;
    }
    if(s[d]=='*'){
        dfs(p,d+1);// 跳过,不匹配,*当作没有
        for(int i=0;i<4;++i)if(c[p][i])
            dfs(c[p][i],d+1),// 匹配,下一个停止用*匹配
            dfs(c[p][i],d); // 匹配,下一个继续用*匹配
        return;
    }
}
int main(){
    scanf("%s%d",s,&n);
    ans=n;len=strlen(s);
    for(int i=1;i<=n;++i)scanf("%s",t),ins(t);
    dfs(0,0);
    printf("%d\n",ans);
}
LG 2536 [AHOI2005]病毒检测
comment评论
Search
search