P2536 [AHOI2005]病毒检测

反思

对于*符号，明明可以让相同位置再次匹配下一个，或者跳过当前位置匹配，但是却写了个把trie的子树全部push进队列的垃圾写法，结果一直MLE

告辞

思路

模板串多且不长，可以塞到trie树里，这个东西貌似叫trie树上模糊匹配？

然后直接bfs爆搜，注意记录一个vis[i][j]，表示第i个节点和第j个位置匹配的情况是否被搜过了，然后小心空间就好了

代码

需要O2

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <bitset>

#include <queue>

using namespace std;

int trie[191000][4],Nodecnt,mark[190010],root,ans=0,lens,n,lent;

char s[1010],t[1010];

bitset<191010> vis[1000];

struct QNode{

    int pos,numNode;

    QNode(int a,int b){

        pos=a,numNode=b;

    }

};

queue<QNode> q;

int to(char c){

    if(c=='A')

        return 0;

    if(c=='G')

        return 1;

    if(c=='C')

        return 2;

    if(c=='T')

        return 3;

}

void insert(char *s,int len){

    int o=root;

    for(int i=1;i<=len;i++){

        if(!trie[o][to(s[i])])

            trie[o][to(s[i])]=++Nodecnt;

        o=trie[o][to(s[i])];

    }

    mark[o]++;

}

void dfs(int pos,int o){

    q.push(QNode(pos,o));

    for(int i=0;i<4;i++)

        if(trie[o][i])

            dfs(pos,trie[o][i]);

}

void query(void){

    q.push(QNode(1,0));//pos Node

    while(!q.empty()){

        QNode x=q.front();

        q.pop();

        if(vis[x.pos][x.numNode])

            continue;

        vis[x.pos][x.numNode]=true;

        // printf("pos=%d numNode=%d\n",x.pos,x.numNode);

        if(x.pos==lens+1){

            ans+=mark[x.numNode];

            continue;

        }

        if(s[x.pos]=='*'){

            q.push(QNode(x.pos+1,x.numNode));

            for(int i=0;i<4;i++)

                if(trie[x.numNode][i])

                    q.push(QNode(x.pos+1,trie[x.numNode][i]));

            for(int i=0;i<4;i++)

                if(trie[x.numNode][i])

                    q.push(QNode(x.pos,trie[x.numNode][i]));

        }

        else if(s[x.pos]=='?'){

            for(int i=0;i<4;i++)

                if(trie[x.numNode][i])

                    q.push(QNode(x.pos+1,trie[x.numNode][i]));

        }

        else{

            if(trie[x.numNode][to(s[x.pos])])

                q.push(QNode(x.pos+1,trie[x.numNode][to(s[x.pos])]));

        }

    }

}

int main(){

    // freopen("5.in","r",stdin);

    scanf("%s",s+1);

    lens=strlen(s+1);

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%s",t+1);

        lent=strlen(t+1);

        insert(t,lent);

    }

    query();

    printf("%d\n",n-ans);

    return 0;

}

巴特西

P2536 [AHOI2005]病毒检测

反思

思路

代码

最新文章

热门文章