hdu 2457&poj 3691 DNA repair ACオートマチック+DP

やってみたら1 Aだったなんて...感動しました....まずn個のウイルスDNA配列を与え,もう一つの長い列を与えた.長さの文字列を少なくともいくつか変更して、ウイルスのシーケンスを1つも含まないようにします.ウイルスの配列を持つACオートマトンを構築し、その後オートマトンでDPを行い、現在の長さがl、オートマトン上の状態がiの場合、最小の文字修正数をdp[l][i]で表す.サイクルA,T,G,Cの4つのスキームは,この文字を追加した後の状態が安全であることを前提として,現在のスキームと親列のl番目がちょうど同じであれば,dp[l+1][tree[i][A,T,G,C]]の最小値を直接dp[l][i]+1で更新し,そうでなければ現在位置の文字を修正する必要があり,すなわち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)
    {
        tt++;
        ac.init();
        for (int i=1; i<=n; i++)
        {
            scanf("%s
",s);
            ac.insert(s,1);
        }
        ac.getFail();
        ac.pushdown();
        scanf("%s
",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
",res);
       else printf("-1
");
    }
    return 0;
}