hdu2457（最少替换多少个字符使主串不包含模式串）ac自动机+dp

题：http://acm.hdu.edu.cn/showproblem.php?pid=2457

题意：给定n个模式串，给定一个主串，问最替换掉多少个字符使主串不包含模式串或输出“-1”表示没有可行的方案；

分析：给n个模式串建立ac自动机，考虑dp[i][j]，表示长度为 i ， j 节点变换为主串前 i 个的最小操作数，j节点要转换必须使当前节点为“安全点”，即end[trie[i][j]]==0;

　　　dp转化就只要不是自己就要在转移过程中+1，i 位置取min 给下一位i+1

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

const int M=2e3+;

const int maxn=;

const int inf=0x3f3f3f3f;

int dp[M][M];

char s[M];

struct ac{

    int trie[M][maxn],fail[M];

    bool end[M];

    int tot,root;

    int newnode(){

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

            trie[tot][i]=-;

        end[tot++]=;

        return tot-;

    }

    void init(){

        memset(end,false,sizeof(end));

        tot=;

        root=newnode();

    }

    int getid(char c){

        if(c=='A')

            return ;

        if(c=='G')

            return ;

        if(c=='T')

            return ;

        if(c=='C')

            return ;

    }

    void insert(char buf[]){

        int now=root,len=strlen(buf);

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

            int id=getid(buf[i]);

            if(trie[now][id]==-)

                trie[now][id]=newnode();

            now=trie[now][id];

        }

        end[now]=true;

    }

    void getfail(){

        queue<int>que;

        while(!que.empty())

            que.pop();

        fail[root]=root;

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

            if(trie[root][i]==-)

                trie[root][i]=root;

            else{

                fail[trie[root][i]]=root;

                que.push(trie[root][i]);

            }

        }

        while(!que.empty()){

            int now=que.front();

            que.pop();

            if(end[fail[now]])

                end[now]=true;

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

                if(trie[now][i]!=-){

                    fail[trie[now][i]]=trie[fail[now]][i];

                    que.push(trie[now][i]);

                }

                else

                    trie[now][i]=trie[fail[now]][i];

            }

        }

    }

}AC;

int main(){

    int n,t=;

    while(~scanf("%d",&n)&&n){

        AC.init();

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

            scanf("%s",s);

            AC.insert(s);

        }

        AC.getfail();

        scanf("%s",s);

        int len=strlen(s);

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

            for(int j=;j<AC.tot;j++)

                dp[i][j]=inf;

        dp[][AC.root]=;

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

            for(int j=;j<AC.tot;j++)

                if(dp[i][j]<inf){

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

                        int now=AC.trie[j][k];

                        if(AC.end[now])

                            continue;

                    //    cout<<now<<"!!"<<endl;

                        int id=AC.getid(s[i]);

                        int add=;

                        if(id!=k)

                            add++;

                        dp[i+][now]=min(dp[i+][now],dp[i][j]+add);

                    //    cout<<dp[i+1][now];

                    }

                }

        int ans=inf;

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

            ans=min(ans,dp[len][i]);

        }

        printf("Case %d: ",++t);

        if(ans==inf)

            puts("-1");

        else

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

    }

    return ;

}