hdu2457 & poj3691 DNA repair AC自动机+DP

         乱搞了一下竟然1A了...太感动了....先给n个病毒DNA序列，再给一个长串。问最少修改长串几个字符，可以让它不包含任何一个病毒序列。拿病毒的序列构造AC自动机，之后再自动机上搞DP，用dp[l][i]表示当前长度为l,自动机上的状态为i时，最少的字符修改数.循环A,T,G,C四种方案，在添加该字符之后的状态为安全的前提下，如果当前方案和母串的第l为刚好相同，那么直接用dp[l][i]去更新dp[l+1][tree[i][A,T,G,C]]的最小值，否则就是需要修改当前位置的字符，即用dp[l][i]+1去更新dp[l+1][tree[i][A,T,G,C]]。dp的初值都赋成inf，dp[0][i]，i是安全状态时赋值为0.循环搞一下，最后从dp[len][i]中找一个最小值输出就行，没最小值就是无解，输出-1。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1020;
const int tk=4;
int tree[maxn][tk];
int val[maxn];
int last[maxn];
int f[maxn];
bool no[maxn];
int n,m,p,q,r,k,t,tt;
int top;
int dp[maxn][maxn];
inline int idx(char s)
{
    if (s=='A') return 0;
    if (s=='T') return 1;
    if (s=='G') return 2;
    if (s=='C') return 3;
}
struct autoAC
{
    void init()
    {
        top=1;
        memset(tree[0],0,sizeof tree[0]);
        memset(val,0,sizeof val);
        memset(f,0,sizeof f);
        memset(last,0,sizeof last);
        memset(no,false,sizeof no);
    }
    void insert(char* s,int rank=1)
    {
        int rt,nxt;
        for (rt=0; *s; rt=nxt,++s)
        {
            nxt=tree[rt][idx(*s)];
            if (nxt==0)
            {
                tree[rt][idx(*s)]=nxt=top;
                memset(tree[top],0,sizeof tree[top]);
                top++;
            }
        }
        val[rt]=rank;
    }
    void getFail()
    {
        queue<int> q;
        f[0]=0;
        for (int c=0; c<tk; c++)
        {
            int u=tree[0][c];
            if (u)
            {
                q.push(u);
                f[u]=0;
                last[u]=0;
            }
        }
        while(!q.empty())
        {
            int r=q.front();
            q.pop();
            for (int c=0;c<tk; c++)
            {
                int u=tree[r][c];
                if (!u)
                {
                    tree[r][c]=tree[f[r]][c];
                    continue;
                }
                q.push(u);
                int v=f[r];
                while(v && !tree[v][c]) v=f[v];
                f[u]=tree[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }
    void pushdown()
    {
        for (int i=0; i<top; i++)
        {
            int j=i;
            while(j)
            {
                no[i]|=val[j];
                j=last[j];
            }
        }
    }
}ac;
char s[30],ss[30],str[1050];

int main()
{
    tt=0;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    while(~scanf("%d\n",&n) && n)
    {
        tt++;
        ac.init();
        for (int i=1; i<=n; i++)
        {
            scanf("%s\n",s);
            ac.insert(s,1);
        }
        ac.getFail();
        ac.pushdown();
        scanf("%s\n",str);
        memset(dp,0x3f3f3f,sizeof dp);
        int nxt;
        int len=strlen(str);
        for (int i=0; i<top; i++)
        if (!no[i])  dp[0][i]=0;

       for (int l=0; l<len; l++)
        for (int i=0; i<top; i++)
        if (no[i]) continue;
        else for (int c=0; c<4;c++)
         {
             nxt=tree[i][c];
             if (no[nxt]) continue;
             if (idx(str[l])==c) dp[l+1][nxt]=min(dp[l+1][nxt],dp[l][i]);
             else dp[l+1][nxt]=min(dp[l+1][nxt],dp[l][i]+1);
         }
       int res=99999;
       printf("Case %d: ",tt);
       for (int i=0; i<top; i++)
       res=min(dp[len][i],res);
       if (res<99999)printf("%d\n",res);
       else printf("-1\n");
    }
    return 0;
}