传送门

题目大意：

给你一个字符主串和很多病毒串，要求更改最少的字符使得没有一个病毒串是主串的子串。

题解：

ac自动机 + dp，用病毒串建好ac自动机，有毒的末尾flag置为true

构建fail指针时，如果fail指针所指节点flag=true，则将当前节点的flag也置为true。

用dp[i][j]表示长度为i的字符串匹配到j节点时最少的更改次数。

这样在ac自动机上跑，若该节点与原串的字符不同则+1

否则+0. 最后扫一遍取flag！=true的dp[len][...]的最小值。

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 55, L = 25, OO = 0x3f3f3f3f;

int n, dp[1005][N * L], tot, len, Case;

char t[L], s[1005];

struct node{

    int trans[5], fail;

    bool flag;

    inline void clear(){

        memset(trans, 0, sizeof trans);

        flag = fail = 0;

    }

}trie[N * L];

inline int getVal(char p){

    if(p == 'A') return 1;

    else if(p == 'C') return 2;

    else if(p == 'G') return 3;

    else return 4;

}

inline void insert(){

    int pos = 1;

    len = strlen(t + 1);

    for(int i = 1; i <= len; i++){

        if(!trie[pos].trans[getVal(t[i])])

            trie[trie[pos].trans[getVal(t[i])] = ++tot].clear();

        pos = trie[pos].trans[getVal(t[i])];

    }

    trie[pos].flag = true;

}

inline void buildFail(){

for(int i = 1; i <= 4; i++) trie[0].trans[i] = 1;

    static int que[N * L], qn;

    que[qn = 1] = 1;

    for(int ql = 1; ql <= qn; ql++){

        int u = que[ql], v, w;

        for(int i = 1; i <= 4; i++){

            v = trie[u].fail;

            while(!trie[v].trans[i]) v = trie[v].fail;

            v = trie[v].trans[i];

            w = trie[u].trans[i];

            if(w){

                trie[w].fail = v, que[++qn] = w;

                if(trie[v].flag)

                    trie[w].flag = true;

            }

            else trie[u].trans[i] = v;

        }

    }

}

inline void solve(){

    len = strlen(s + 1);

    for(int i = 1; i <= len; i++)

        for(int j = 1; j <= tot; j++)

            dp[i][j] = OO;

    dp[0][1] = 0;

    for(int i = 1; i <= len; i++)

        for(int j = 1; j <= tot; j++){

            if(dp[i - 1][j] == OO) continue;

            for(int k = 1; k <= 4; k++){

                int u = trie[j].trans[k];

                if(trie[u].flag) continue;

                dp[i][u] =  min(dp[i][u], dp[i - 1][j] + (getVal(s[i]) != k));

            }

        }

    int ans = OO;

    for(int i = 1; i <= tot; i++){

        if(dp[len][i] == OO) continue;

        ans = min(ans, dp[len][i]);

    }

    printf("Case %d: %d\n", ++Case, ans < OO ? ans: -1);

}

int main(){

    while(scanf("%d", &n), n){

        trie[tot = 1].clear();

        for(int i = 1; i <= n; i++){

            scanf("%s", t + 1);

            insert();

        }

        buildFail();

        scanf("%s", s + 1);

        solve();

    }

    return 0;

}