题目链接:http://poj.org/problemstatus?problem_id=3691

题目大意

给定一系列代表疾病的DNA序列,同时已知一条DNA序列,计算改变最少的DNA序列来使这个DNA序列不包含疾病的DNA序列

例如:

AAA
AAG
#前面两列代表疾病的DNA序列

AAAG #正常的DNA序列

输出:1     #修改第三个字符即可

解题思路

AC自动机+状态dp
首先由desease的DNA序列,构造出Trie树即AC自动机,也可以叫做DFA图,每个节点代表一种状态,然后利用状态转移的动态规划方法,dp[i][j] 表示到目标串的第 i 个字符,DFA 状态为 j 时的最小修改数量,具体方程分为两种,已知dp[i-1][j]:
1,child[sequence[i]] 状态j的匹配第i个字符的子节点 && !is_danger
dp[i][child[sequence[i]]] = min{dp[i][child[sequence[j]]], dp[i-1][j]}
2,状态j的其他子节点 && is_danger
dp[i][other_child] = min{dp[i][other_child], dp[i-1][other_child] + 1}

最后在所有的dp[len-1][j] &&!is_danger 中找到 最小的值极为所求

/*
 * Author: liyangguang <liyangguang@software.ict.ac.cn>
 * http://www.yaronspace.cn/blog
 *
 * File: 3691.cc
 * Create Date: 2010-11-14 20:34:41
 *
 */
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <vector>
#include <stdio.h>
#include <string.h>
#define MAX_STR_LEN 1001
#define MAX_NODES 800
using namespace std;
struct TrieNode {
    TrieNode *next[4];     
    TrieNode *fail;
    // 是否是边界
    int isdanger;
    int index;
    TrieNode():fail(0),isdanger(0),index(0)
    {
        memset(next, 0, sizeof(next));
    }
};
class TrieTree
{
    public:
        TrieNode *root;
        vector<TrieNode *> node_list;
        TrieTree():root(0) { Init();}
        void Init();
        void Insert(const string& str);
        // 构造fail指针
        void BuildTrieTree();
        virtual ~TrieTree();
 
};
inline int id(char ch)
{
    switch (ch) {
        case 'A':return 0;
        case 'T':return 1;
        case 'G':return 2;
        case 'C':return 3;
    }
}
void
TrieTree::Init()
{
    root = new TrieNode();
    root->index = 0;
    node_list.push_back(root);
}
void
TrieTree::Insert(const string& str)
{
    int size = str.size();
    TrieNode *r = root;
    int i = 0, j = 0;
    for (j = 0; j < size; ++j) {
        i = id(str[j]);
        if (r->next[i] == NULL) {
            r->next[i] = new TrieNode();
            r->next[i]->index = node_list.size();
            node_list.push_back(r->next[i]);
        }
        r = r->next[i];
    }
    r->isdanger = 1;
}
void 
TrieTree::BuildTrieTree()
{
    TrieNode* r = root, *p;
    queue<TrieNode *> q;
    root->fail = root;
    q.push(root);
    int i = 0;
    while (!q.empty()) {
        p = q.front();
        q.pop();
        p->isdanger = p->isdanger || p->fail->isdanger;
        for (i = 0; i < 4; ++i) {
            if (p->next[i] == NULL) {
                p->next[i] = (p == root) ? root : p->fail->next[i];
            }
            else
            {
                p->next[i]->fail = (p == root) ? root : p->fail->next[i];
                q.push(p->next[i]);
            }
        }
 
    }
}
 
TrieTree::~TrieTree()
{
    vector<TrieNode *>::iterator itr;
    itr = node_list.begin();
    for(; itr != node_list.end();++itr) {
        delete *itr;
    }
    node_list.clear();
}
void 
checkmin(int& a,int b) {
    if(a==-1) a=b;
    else if(a>b) a=b;
}
//记录状态方程的信息
int dp[MAX_STR_LEN][MAX_NODES] = {0};
int
build_dp(const string &sequences, TrieTree *tree) 
{
    unsigned int i, j, k;
    memset(dp, -1, sizeof(dp));
    if (!tree->node_list[0]->next[id(sequences[0])]->isdanger) {
        dp[0][tree->node_list[0]->next[id(sequences[0])]->index] = 0;
    }
    for (i = 0;i < 4; ++i) {
        if (i != id(sequences[0]) && !tree->node_list[0]->next[i]->isdanger) {
            dp[0][tree->node_list[0]->next[i]->index] = 1;
        }
    }
    for (i = 1;i < sequences.size(); ++i) {
        for (j = 0;j < tree->node_list.size(); ++j) {
            if (dp[i-1][j] != -1)
            {
                if (!tree->node_list[j]->next[id(sequences[i])]->isdanger) {
                    checkmin(dp[i][tree->node_list[j]->next[id(sequences[i])]->index], dp[i-1][j]); 
                }
                for (k = 0; k < 4; ++k) {
                    if (k != id(sequences[i]) && !tree->node_list[j]->next[k]->isdanger) {
                        checkmin(dp[i][tree->node_list[j]->next[k]->index], dp[i-1][j]+1);
                    }
                }
            }
 
        }
    }
    int ans = 1<<20;
    for (i = 0;i < tree->node_list.size();++i) {
        if (!tree->node_list[i]->isdanger && dp[sequences.size() - 1][i] != -1&& dp[sequences.size() - 1][i] < ans)
            ans = dp[sequences.size() - 1][i];
    }
    return ans == 1<<20 ? -1 : ans; 
}
int 
main(int argc, char* argv[])
{
    int cases = 1, n = -1, i = 0;
    string disease, seq;
    while (cin >>n && n != 0) {
        TrieTree *tree = new TrieTree();
        for (i = 0;i < n; ++i) {
            cin >>disease;
            tree->Insert(disease);
        }
        tree->BuildTrieTree();
        cin >> seq;
        printf("Case %d: %d\n",cases++, build_dp(seq, tree));
        delete tree;
    }
    return 0;
}
 
/* vim: set ts=4 sw=4: */
来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/959