【Luogu】P2536病毒检测（Trie上DP）

　　题目链接

　　这道题我写了个01DP,f[i][j]表示跑到Trie上第i个节点，匹配到字符串第j位行不行

　　然后重点在*号无限匹配怎么处理

　　经过一番脑洞我们可以发现*号无限匹配可以拆成两种情况：

　　1：匹配数无条件+1，但是字符串仍然匹配到底j位

　　2：直接跳过去了qwq

　　对应设计状态转移方程就好了

　　然后这个算法……我卡时卡空间勉强过

　　卡时不知道怎么办……也许能循环展开什么的？

　　卡空间的话，可以设滚动数组。

　　f[i][j]中的i不再代表Trie上第i个节点，而是代表深度第i层的节点

　　DP的时候用dfs的方法DP，DP完了统计一下就可以把原来叶子占用的空间清掉腾给别人

　　Orz rqy，这真是个神办法

// luogu-judger-enable-o2

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cctype>

#include<queue>

#define maxn 505

#define maxl 1020

using namespace std;

int tree[maxn*maxn][],tot;

int fail[maxn*maxn];

char s[maxl];

char c[maxl];

int pnt[maxn];

bool f[][maxn];

inline int count(char i){

    if(i=='A')    return ;

    if(i=='T')    return ;

    if(i=='C')    return ;

    if(i=='G')    return ;

    if(i=='*')    return ;

    return ;

}

void update(int x){

    int n=strlen(c+),now=;

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

        if(tree[now][count(c[i])]==)    tree[now][count(c[i])]=++tot;

        now=tree[now][count(c[i])];

    }

    pnt[x]=now;

    return;

}

void makefail(){

    queue<int>q;

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

        if(tree[][i])    q.push(tree[][i]);

    while(!q.empty()){

        int from=q.front();    q.pop();

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

            int &now=tree[from][i];

            if(now==){

                now=tree[fail[from]][i];

                continue;

            }

            fail[now]=tree[fail[from]][i];

            q.push(now);

        }

    }

    return;

}

int main(){

    scanf("%s",s+);int len=strlen(s+);

    int n;    scanf("%d",&n);

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

        scanf("%s",c+);

        update(i);

    }

    //makefail();

    f[][]=;

    for(int i=;i<=tot;++i){

        for(register int j=;j<len;++j){

            if(s[j+]=='A')    if(tree[i][])    f[tree[i][]][j+]|=f[i][j];

            if(s[j+]=='T')    if(tree[i][])    f[tree[i][]][j+]|=f[i][j];

            if(s[j+]=='C')    if(tree[i][])    f[tree[i][]][j+]|=f[i][j];

            if(s[j+]=='G')    if(tree[i][])    f[tree[i][]][j+]|=f[i][j];

            if(s[j+]=='?')

                for(int k=;k<;++k)

                    if(tree[i][k])    f[tree[i][k]][j+]|=f[i][j];

            if(s[j+]=='*'){

                f[i][j+]|=f[i][j];

                for(int k=;k<;++k)

                    if(tree[i][k])    f[tree[i][k]][j]|=f[i][j];

            }

        }

        for(int j=;j<;++j)    f[tree[i][j]][len]|=f[i][len];

    }

    int ans=n;

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

        if(f[pnt[i]][len]==)    ans--;

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

    return ;

}

/*

A*G?C

3

AGTC

AGTGTC

AGTGC

*/

巴特西

【Luogu】P2536病毒检测（Trie上DP）

最新文章

热门文章