icontofig | 发布于 2020-01-14 18:21:16 | 阅读量 727 | DP 字符串
发布于 2020-01-14 18:21:16 | DP 字符串

题目大意

给出n个模式串和一个匹配串,求问最少要修改匹配串中多少个字符才能使得匹配串中不含有任意一个模式串。

题解

多个模式串一定要用AC自动机的

所以首先把AC自动机给建出来

然后在AC自动机上跑DP,dp[i][j]表示当前匹配到长度为i,在AC自动机的Trie树上走到节点j的状态下的所需要修改的字符数量的最小值。

要注意不能走到模式串结尾的节点上。

在转移的时候,从当前状态向其子节点转移(前提是子节点非模式串结束的位置对应的节点),如果转移的节点的字符与字符串下一个字符相同,那么下一个状态的dp值继承当前状态dp值,代表不修改下一个字符的情况;否则下一个状态的dp值要在当前状态的dp值的基础上+1,表示修改下一个字符。

最后对dp[len][i]的所有值取min,即为最终答案。

(做这个题主要是为了写一遍AC自动机的板子)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int INF = (1<<30)-1;
struct AC_auto{
    int next[4];
    bool flag;
    int fail;
}tr[maxn];
int root;
int index = 0;
int newnode(bool f){
    tr[index].flag = f;
    tr[index].fail = 0;
    for(int i = 0;i < 4;++i){
        tr[index].next[i] = 0;
    }
    return index++;
}
int n;
char ss[maxn];
int change(char c){
    switch(c){
        case 'A' : return 0;break;
        case 'T' : return 1;break;
        case 'G' : return 2;break;
        default : return 3;break;
    }
    return 0;
}
void build(char *s){
    int now = root;
    int len = strlen(s);
    for(int i = 0;i < len;++i){
        int t = change(s[i]);
        if(tr[now].next[t] == 0)
            tr[now].next[t] = newnode((i == len-1));
        now = tr[now].next[t];
        if(i == len-1)
            tr[now].flag = 1;
    }
    return;
}
queue<int>q;
void pre_fail(){
    tr[root].fail = root;
    for(int i = 0;i < 4;++i){
        if(tr[root].next[i]){
            tr[tr[root].next[i]].fail = root;
            q.push(tr[root].next[i]);
        }
    }
    while(!q.empty()){
        int pos = q.front();q.pop();
        for(int i = 0;i < 4;++i){
            if(tr[pos].next[i]){
                int j = tr[pos].fail;
                while(j > 0 && !tr[j].next[i])
                    j = tr[j].fail;
                if(tr[j].next[i])
                    j = tr[j].next[i];
                tr[tr[pos].next[i]].fail = j;
                if(tr[tr[tr[pos].next[i]].fail].flag)
                    tr[tr[pos].next[i]].flag = true;
                q.push(tr[pos].next[i]);
            }
            else
                tr[pos].next[i] = tr[tr[pos].fail].next[i];
        }
    }
    return;
}
int dp[maxn][maxn];
int solve(char *s,int len){
    for(int i = 0;i <= len;++i){
        for(int j = 0;j < index;++j)
            dp[i][j] = INF;
    }
    dp[0][0] = 0;
    for(int i = 1;i <= len;++i){
        for(int j = 0;j < index;++j){
            if(tr[j].flag)continue;
            if(dp[i-1][j] == INF)continue;
            for(int k = 0;k < 4;++k){
                int r = tr[j].next[k];
                if(tr[r].flag)continue;
                dp[i][r] = min(dp[i][r],dp[i-1][j] + (change(s[i-1]) != k));
            }
        }
    }
    int ans = INF;
    for(int i = 0;i < index;++i)
        ans = min(ans,dp[len][i]);
    return (ans == INF) ? -1 : ans;
}
int main(){
    int cas = 0;
    while(scanf("%d",&n) != EOF && n){
        index = 0;
        root = newnode(0);
        for(int i = 0;i < n;++i){
            scanf("%s",ss);
            build(ss);
        }
        pre_fail();
        scanf("%s",ss);
        printf("Case %d: %d\n",++cas,solve(ss,strlen(ss)));
    }
    return 0;
}



内容更新于: 2020-01-14 18:21:21
链接地址: http://blog.leanote.com/post/icontofig/daa0f3cac49a

上一篇: Educational Codeforces Round 80 (Rated for Div. 2) E Messenger Simulator 树状数组求区间内不同的数的个数

下一篇: Codeforces 609 div1B Domino for Young 思维题

727 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航