HDU 2457

题意略。

思路：

由求出最小修改字符个数可知，这应该是一个dp，当长度为i + 1的串想利用上长度为i的串的时候，我们是需要知道前几个字符的，以防出现错误基因串。

然而我们得到的长度为i的合法字符串不知道会被改成什么样子，所以我们可以给它分个类，假设它以这些错误基因串的前缀结尾的话，

应该有sum(L1 + L2 + ... + Ln) + 1种，+1表示有可能存在多个哪种都不属于的情况，由于此时我们填什么字符都无所谓了，所以就算作一种。

则dp[i][j]表示：一个长度为i的前缀被改成第以j种情况结尾，至少要更改几次（且这个串为合法串）。

这里我们预处理出trie图，用于状态的转移，在dp时我们使用刷表法。

详见代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int F = 0x3f;
const int INF = 0x3f3f3f3f;

int n;
char buf[maxn];
int str[maxn];
int dp[maxn][maxn];
int mp[300];

struct ac_auto{
    int relation[maxn][4],fail[maxn],infor[maxn];
    int root,l;
    int newnode(){
        memset(relation[l],-1,sizeof(relation[l]));
        infor[l++] = 0;
        return l - 1;
    }
    void init(){
        l = 0;
        root = newnode();
    }
    void insert(char buf[]){
        int len = strlen(buf);
        int cur = root;
        for(int i = 0;i < len;++i){
            int hash = mp[buf[i]];
            if(relation[cur][hash] == -1)
                relation[cur][hash] = newnode();
            cur = relation[cur][hash];
        }
        ++infor[cur];
    }
    void build(){
        queue<int> que;
        fail[root] = root;
        for(int i = 0;i < 4;++i){
            if(relation[root][i] == -1) relation[root][i] = root;
            else{
                fail[relation[root][i]] = root;
                que.push(relation[root][i]);
            }
        }
        while(que.size()){
            int cur = que.front();
            que.pop();
            /***************************************/
            if(infor[fail[cur]]) infor[cur] += 1;
            /***************************************/
            for(int i = 0;i < 4;++i){
                if(relation[cur][i] == -1){
                    relation[cur][i] = relation[fail[cur]][i];
                }
                else{
                    fail[relation[cur][i]] = relation[fail[cur]][i];
                    que.push(relation[cur][i]);
                }
            }
        }
    }
};

ac_auto ac;

int main(){
    int cas = 1;
    mp['A'] = 0,mp['T'] = 1,mp['C'] = 2,mp['G'] = 3;
    while(scanf("%d",&n) == 1 && n){
        ac.init();
        memset(dp,F,sizeof(dp));
        for(int i = 0;i < n;++i){
            scanf("%s",buf);
            ac.insert(buf);
        }
        ac.build();
        scanf("%s",buf);
        int len = strlen(buf);
        dp[0][0] = 0;
        int state = ac.l;
        for(int i = 0;i < len;++i){
            for(int j = 0;j < state;++j){
                if(dp[i][j] == INF) continue;
                for(int k = 0;k < 4;++k){
                    int nxt = ac.relation[j][k];
                    if(ac.infor[nxt]) continue;
                    int add = (mp[buf[i]] == k) ? 0 : 1;
                    dp[i + 1][nxt] = min(dp[i + 1][nxt],dp[i][j] + add);
                }
            }
        }
        int ans = INF;
        for(int i = 0;i < state;++i){
            ans = min(ans,dp[len][i]);
        }
        printf("Case %d: %d
",cas++,ans == INF ? -1 : ans);
    }
    return 0;
}

注意被注释包围的那一行，由于我们在转移时，都是转移到最长的匹配串。有可能转移到的这个串不是非法的，而它的后缀是非法的，这时我们也同样要将

它视为非法的字符串。

然而，在正常的ac自动机查询时，这一段代码是不能加的，会导致重复计算。