欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

HDU 2457 AC 自动机 + DP

程序员文章站 2024-01-24 15:45:28
题意传送门 HDU 2457题解初始化 ACACAC 自动机,将 TrieTrieTrie 上节点看做字符串后缀的不同模式(或者状态)。若一个模式存在目标基因,那么这个节点或其失配节点(最长前缀)对应的字符串是目标基因。计算失配指针的时候,处理了各节点的所有状态转移(即在字符串结尾添加 A,C,G,TA,C,G,TA,C,G,T 其中一个字符),同时标记各状态是否存在目标基因即可。dp[i+1][j]dp[i+1][j]dp[i+1][j] 代表字符串在区间 [0,i][0,i][0,i] 且后缀模...
题意

传送门 HDU 2457

题解

初始化 A C AC AC 自动机,将 T r i e Trie Trie 上节点看做字符串后缀的不同模式(或者状态)。若一个模式存在目标基因,那么这个节点或其失配节点(最长后缀)对应的字符串是目标基因。计算失配指针的时候,处理了各节点的所有状态转移(即在字符串结尾添加 A , C , G , T A,C,G,T A,C,G,T 其中一个字符),同时标记各状态是否存在目标基因即可。

d p [ i + 1 ] [ j ] dp[i+1][j] dp[i+1][j] 代表字符串在区间 [ 0 , i ] [0,i] [0,i] 且后缀模式为状态 j j j 的最少处理次数,设原始字符串为 s t r str str 则有

d p [ i + 1 ] [ t r i e [ j ] [ k ] ] = { d p [ i ] [ j ] s t r [ i ] 等 于 k 代 表 的 字 符 d p [ i ] [ j ] + 1 o t h e r w i s e dp[i+1][trie[j][k]]=\begin{cases} dp[i][j] & str[i]等于k代表的字符\\ dp[i][j]+1 & otherwise \\ \end{cases} dp[i+1][trie[j][k]]={dp[i][j]dp[i][j]+1str[i]kotherwise

状态转移时要保证各状态代表的后缀模式不存在目标基因,不合法状态设为 I N F INF INF,初始为空串,满足条件,则有 d p [ 0 ] [ 0 ] = 0 dp[0][0]=0 dp[0][0]=0

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 1005
int ns, id['Z' + 1], trie[maxn][4], flag[maxn], fail[maxn], dp[maxn][maxn];
char str[maxn];

void insert(char *s)
{
    int len = strlen(s), p = 0;
    for (int i = 0; i < len; i++)
    {
        int c = id[s[i]];
        if (!trie[p][c])
        {
            memset(trie[ns], 0, sizeof(trie[ns]));
            trie[p][c] = ns++;
        }
        p = trie[p][c];
    }
    flag[p] = 1;
}

void getFail()
{
    queue<int> q;
    for (int i = 0; i < 4; i++)
    {
        if (trie[0][i])
        {
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        if (flag[fail[p]])
        {
            flag[p] = 1;
        }
        for (int i = 0; i < 4; i++)
        {
            if (trie[p][i])
            {
                fail[trie[p][i]] = trie[fail[p]][i];
                q.push(trie[p][i]);
            }
            else
            {
                trie[p][i] = trie[fail[p]][i];
            }
        }
    }
}

int main()
{
    int n, t = 0;
    while (~scanf("%d", &n) && n)
    {
        ns = 1, id['A'] = 0, id['C'] = 1, id['G'] = 2, id['T'] = 3;
        memset(trie[0], 0, sizeof(trie[0]));
        memset(flag, 0, sizeof(flag));
        char s[25];
        for (int i = 0; i < n; i++)
        {
            scanf(" %s", s);
            insert(s);
        }
        getFail();
        scanf(" %s", str);
        int len = strlen(str);
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < ns; j++)
            {
                for (int k = 0; k < 4; k++)
                {
                    int nxt = trie[j][k];
                    if (!flag[j] && !flag[nxt])
                    {
                        dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j] + (k == id[str[i]] ? 0 : 1));
                    }
                }
            }
        }
        int res = len + 1;
        for (int i = 0; i < ns; i++)
        {
            if (!flag[i])
            {
                res = min(res, dp[len][i]);
            }
        }
        printf("Case %d: %d\n", ++t, res > len ? -1 : res);
    }
    return 0;
}

本文地址:https://blog.csdn.net/neweryyy/article/details/108589714

相关标签: AC 自动机 DP