Poj 3691 & Hdu 2457 DNA repair

解題思路：

AC自動機+DP

dp[ i ][ j ]表示主串比對到了第 i 個位置，然後到達的是AC自動機上的 j 狀态（可以了解為Trie樹的節點位置）時最少修改字元的個數，我們保證 j 狀态不是模式串（ DNA病毒串）的結束節點，然後不斷地往後走選出一條比對完主串，并且修改字元串數最少的的一條。

狀态轉移為dp[ i ][ j ] = min( dp[ i ][ j ] , dp[ i-1 ][ j ] + ( idx( str[ i-1 ] ) != idx( k ) ) )  表示讀到 i 個字元時，對應于 j 狀态（DP的過程兩重循環 i 和 j ），要轉移到 child[ j ]（j的子節點狀态，在這裡用k∈[0,3]一重循環周遊所有可以轉的兒子），如果第i個字元跟所要轉移到的字元相同，則代價為0，因為不需要改變；否則代價為1，因為需要改變。

注意：

為每個結點構造失敗指針的同時，檢查其失敗指針所指向的節點是否為危險節點，如果是的話也需要把目前節點标記為危險節點。

在dp的時候：如果子節點為危險節點，則不可以進行轉移。

最後，循環dp[ len ][ j ] ,j∈[0,size-1]，即在讀完最後一個字元後檢查所有狀态的最終值，取其最小。如果均不可達，則傳回-1。

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define eps 1e-9
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

const int MAXPT=500007;   //最大節點數
const int size=4;     //子節點數

class Ac_Automat
{
private:
    struct Node
    {
        Node *fail;
        Node *next[size];
        bool flag;
        int id;
        void newnode () //生成節點
        {
            fail=NULL;
            for (int i=0; i<size; i++)
                next[i]=NULL;
            flag=false;
        }
    };

    Node *q[MAXPT],H[MAXPT],*root;
    int ID[128];
    int fr,tl,t;
public:

    int dp[1005][1005];
    void Init ()
    {
        fr = tl = 0;
        t = 0;
        H[t].newnode();
        H[t].id=t;  //對Trie樹上的每一個節點給一個狀态号
        root = &H[t++];
        ID['A']=0;
        ID['G']=1;
        ID['C']=2;
        ID['T']=3;
    }

    void Insert (const char *str)
    {
        Node *cur = root;
        for (const char *p=str; *p; p++)
        {
            int k=ID[*p];
            if (cur->next[k] == NULL)
            {
                H[t].newnode();
                H[t].id = t;//給定狀态的編号
                cur->next[k] = &H[t++];
            }
            cur = cur->next[k];
        }
        cur->flag=true;   //是單詞結束
    }

    void Build()
    {
        root->fail = NULL;
        q[tl] = root;
        while (fr <= tl)
        {
            Node *tmp = q[fr++];

            //這裡解決出現aact  aac這種情況，隻要包含aac就是非法的的有病毒的
            if (tmp != root)
                tmp->flag = tmp->flag||tmp->fail->flag;

            for (int i=0; i<size; i++)
            {
                //這裡要更新每一個next為空的指針,用來循環比對
                if (tmp->next[i] == NULL)
                {
                    if (tmp == root) tmp->next[i] = root;
                    else tmp->next[i] = tmp->fail->next[i];
                }
                else//構造比對失敗指針
                {
                    if (tmp == root)
                        tmp->next[i]->fail = root;
                    else
                    {
                        Node *p = tmp->fail;
                        while (p != NULL)
                        {
                            if (p->next[i])
                            {
                                tmp->next[i]->fail = p->next[i];
                                break;
                            }
                            p = p->fail;
                        }
                        if (p == NULL)
                            tmp->next[i]->fail = root;
                    }
                    q[++tl] = tmp->next[i];
                }
            }
        }
    }

    int Deal(const char *str)
    {
        int len = strlen(str);

        for (int i=0; i<=len; i++)
            for (int j=0; j<t; j++)
                dp[i][j]=INF;
        dp[0][0]=0;

        for (int i=0; i<len; i++) for (int j=0; j<t; j++) //走主串,枚舉每一個狀态
                if (dp[i][j]!=INF && H[j].flag==false)  //該狀态合法
                {
                    for (int k=0; k<size; k++) //枚舉可走的邊
                    {
                        if (H[j].next[k]->flag)
                            continue;
                        int add=(k !=ID[str[i]]);
                        dp[i+1][H[j].next[k]->id] = min(dp[i+1][H[j].next[k]->id], dp[i][j]+add);
                    }
                }
        int ans=-1;
        for (int i=0; i<t; i++)
            if (dp[len][i]!=INF && (ans==-1 || dp[len][i]<ans))
                ans = dp[len][i];
        return ans;
    }
} ac;

char str[1005],s[25];

int main ()
{
    int n,Cas=0;
    while(read(n)&&n)
    {
        ac.Init();
        for (int i=1; i<=n; i++)
            scanf("%s",s),ac.Insert(s);
        scanf("%s",str);
        ac.Build();
        printf("Case %d: %d\n",++Cas,ac.Deal(str));
    }
    return 0;
}