HDU 2457 AC 自动机 + DP

题意

传送门 HDU 2457

题解

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

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

$$dp[i+1][trie[j][k]]=\{\begin{array}{ll}dp[i][j]& str[i]等于k代表的字符\\ dp[i][j]+1& otherwise\end{array}$$

状态转移时要保证各状态代表的后缀模式不存在目标基因，不合法状态设为 $INF$，初始为空串，满足条件，则有 $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