默认已经学习了ac自动机, 这里主要分析y总代码里面的dp部分

重点:

任何trie图里面的idx都可能是路径的终点

f[i][j] 表示的是走到字符串第i个字符, 终点停在j的代价最小的走法,

而且在这堆走法里面这个字符有可能被改变了也有可能没变

另外一个有点绕的地方是j循环, 里面的j其实是枚举起点, 我们实际上更新了的数据是j经过选择k之后的下一个节点f[i+1][p]

// 从f[0][0] 出发, 也就从idx为0能到的节点被成功min了
// 然后再从那些成功被min的点才能继续往后走
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < m; i++)
{
    for (int j = 0; j <= idx; j++)  //j从0出发是根节点出发
    {
        for (int k = 0; k < 4; k++)
        {
            // 判断下个字符是不是当前k, 
            // 若果是的话, 那么就表示当前字符不需要更改就能往下走, 这一步的t = 0; 
            // 如果不是k的话, 要往k这个点走, 则需要更改, 这一步的代价t等于1
            // 注意更改的是str
            int t = get_num[str[i+1]] != k; 

            int p = tr[j][k];  //当前起点idx j选择k路线之后的下个点的idx

            if (!dar[p]) // 有标记的点都是不能走的
                // 从字符str[i]到str[i+1], 从所有的idx(也就是j)各自的4条路里面合法的路径,
                // 走一步, 选其中代价最小的
                f[i+1][p] = min(f[i+1][p], f[i][j] + t);
        }

    }
}

由于要遍历完整个str, 一共会有idx种j终点取法, 所以最后还得取个min才能得到res:

int res = 0x3f3f3f3f;
for (int i = 0; i <= idx; i++) res = min(res, f[m][i]);

回到刚才的dp, 其实理解了之后我们可以发现有很大一部分j的遍历是无效的:

1. 那些从f[0][0]到达不了的点,都是没有被dp更改过的, 而这些点都还是初始值0x3f3f3f3f, 显然他们都不能作为从i到i+1的j起点, 于是可以在j循环里面加上 if (i && f[i][j] == 0x3f3f3f3f) continue;
2. 而另外, 不能作为终点的dar[j]为1的点显然也不可能是起点, 于是又可以在j循环里面加上 if (dar[j]) continue;

改进后的dp部分如图:

// 任何trie图里面的idx都可能是路径的终点
// f[i][j] 表示的是走到字符串第i个字符, 终点停在j的代价最小的走法, 
// 而且在这堆走法里面这个字符有可能被改变了也有可能没变
// 从f[0][0] 出发, 也就从idx为0能到的节点被成功min了
// 然后再从那些成功被min的点才能继续往后走
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < m; i++)
{
    for (int j = 0; j <= idx; j++)  //j从0出发是根节点出发
    {
        if (dar[j]) continue;  // 不能到这种点, 自然也不能从这种点出发

        // 从i到i+1, 就是再往前走一个字符, 那么自然我们就只能从已经能走到的点出发,
        // 那么他们的f值就肯定不是无穷
        if (i && f[i][j] == 0x3f3f3f3f) continue;

        for (int k = 0; k < 4; k++)
        {
            // 判断下个字符是不是当前k, 
            // 若果是的话, 那么就表示当前字符不需要更改就能往下走, 这一步的t = 0; 
            // 如果不是k的话, 要往k这个点走, 则需要更改, 这一步的代价t等于1
            // 注意更改的是str
            int t = get_num[str[i+1]] != k; 

            int p = tr[j][k];  //当前起点idx j选择k路线之后的下个点的idx

            if (!dar[p]) // 有标记的点都是不能走的
                // 从字符str[i]到str[i+1], 从所有的idx(也就是j)各自的4条路里面合法的路径,
                // 走一步, 选其中代价最小的
                f[i+1][p] = min(f[i+1][p], f[i][j] + t);
        }

    }
}

完整 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1010;
using namespace std;

int n, m;
int tr[N][4], dar[N], idx;
int q[N], ne[N];
char str[N];
int f[N][N];
int get_num[128];  // 数组优化get




void insert()
{
    int p = 0; 
    for (int i = 0; str[i]; i++)
    {
        int t = get_num[str[i]];
        if (!tr[p][t])
        {
            tr[p][t] = ++idx;
        }
        p = tr[p][t];
    }
    dar[p] = 1;

}

void build()
{
    int front = 0, rear = 0;
    for (int i = 0; i < 4; i++) if (tr[0][i]) q[rear++] = tr[0][i];

    while (front < rear)
    {
        int t = q[front++];
        for (int i = 0; i < 4; i++)
        {
            int c = tr[t][i];
            if (!c) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[c] = tr[ne[t]][i];
                q[rear++] = c;
                dar[c] |= dar[ne[c]]; // 加上这行因为某序列的子序列可能包含了病毒序列
                                      // 比如accgt和cg
            }
        }
    }

}

int main()
{
    get_num['A'] = 0, get_num['T'] = 1, get_num['G'] = 2, get_num['C'] = 3;

    int T = 1;
    while (scanf("%d", &n), n)
    {
        memset(tr, 0, sizeof tr);
        memset(dar, 0, sizeof dar);
        memset(ne, 0, sizeof ne);
        idx = 0;


        for (int i = 0; i < n; i++)
        {
            scanf("%s", str);
            insert();
        }

        build();


        scanf("%s", str + 1);
        m = strlen(str+1);

        // 任何trie图里面的idx都可能是路径的终点
        // f[i][j] 表示的是走到字符串第i个字符, 终点停在j的代价最小的走法, 
        // 而且在这堆走法里面这个字符有可能被改变了也有可能没变

        // 从f[0][0] 出发, 也就从idx为0能到的节点被成功min了
        // 然后再从那些成功被min的点才能继续往后走
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j <= idx; j++)  //j从0出发是根节点出发
            {
                if (dar[j]) continue;  // 不能到这种点, 自然也不能从这种点出发

                // 从i到i+1, 就是再往前走一个字符, 那么自然我们就只能从已经能走到的点出发,
                // 那么他们的f值就肯定不是无穷
                if (i && f[i][j] == 0x3f3f3f3f) continue;  
                for (int k = 0; k < 4; k++)
                {
                    // 判断下个字符是不是当前k, 
                    // 若果是的话, 那么就表示当前字符不需要更改就能往下走, 这一步的t = 0; 
                    // 如果不是k的话, 要往k这个点走, 则需要更改, 这一步的代价t等于1
                    // 注意更改的是str
                    int t = get_num[str[i+1]] != k; 

                    int p = tr[j][k];  //当前起点idx j选择k路线之后的下个点的idx

                    if (!dar[p]) // 有标记的点都是不能走的
                        // 从字符str[i]到str[i+1], 从所有的idx(也就是j)各自的4条路里面合法的路径,
                        // 走一步, 选其中代价最小的
                        f[i+1][p] = min(f[i+1][p], f[i][j] + t);
                }

            }
        }


        int res = 0x3f3f3f3f;
        for (int i = 0; i <= idx; i++) res = min(res, f[m][i]);
        if (res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", T++, res);
    }
    return 0;
}