Visits: 168

计蒜客 – 情报加密

蒜头君是我军的情报专家，现在我军有一份重要情报要发送出去，这是一份特别重要的情报，一旦被敌军截获，里面有一些重要的片段会暴露我们的身份，所以蒜头君需要改变一些字符，这样即使敌军截获了我们的情报，也无法获得正确信息。

比如，情报中如果包含 AAB, ABC 和 CAB 就会暴露我们的身份，但是情报中的 AABCAB 把这三个片段都包含了，不过我们只需改变两个字符使其变成 ABBCAB，这样就不会暴露任意一个关键片段信息了。注意，我们的情报中只包含 A, B, C, D 这四个字母，我们修改时也只能使用这四个字母。

你要帮助蒜头君通过改变最少的字符来加密情报。

输入格式

第一行一个整数 $n$ $(n\leq 50)$，表示可能关键的情报段数量。

接下来 $n$ 行，每行一个长度不超过 $20$ 的字符串，由 A，B，C 和 D构成。

最后一行，一个长度不超过 $10^3$ 的字符串是，由 A，B，C 和 D 构成。

2
A
DB
DBAADB

输出格式

一行一个整数，表示最少修改字符的数量。若无解，则输出 $-1$。

4

这道题是想要我们求出对于一个给定的字符串，至少修改多少次可以使得该字符串不出现任何一个字典中的子串。

解决方法是使用 AC 自动机 + 动态规划。

这题字符范围只有 A ~ D，所以 MAXC = 4，其余的 AC 自动机的部分不需要修改，直接套用模板，依然只需要修改 solve() 函数。

我们定义 dp[][] 数组用来动态规划。

状态的定义 dp[i][p] 表示对于情报中前 i 个字符组成的串，在结点 p 的时候，最少需要修改多少次才能满足要求。

初始化只需要设定 dp[0][0] = 0，因为对于空串，显然不需要修改。

下面我们考虑状态转移。

现在我站在 p 这个节点，手上已经有了情报的前 i 个字符，而且已经知道了修改多少次能够使情报更安全。为了构造一个不包含关键情报的串，我现在可以在前缀树中沿着边走，即选择 child[p] 中的一者，走下去，走一步，情报长度就会加一。当遇到某个结点 child[p][C] 是一个单词的结束时（sta[child[p][C]] == true），说明不能走这条路，要换一条，即可以尝试 child[p][A] 或者 child[p][B] 等。

那么，i 只能转移到 i + 1，p 只能转移到 child[p]['A'] ~ child[p]['D'] 四者之一。

其中，如果 sta[child[p][x]] 为 true，说明那里是一个关键情报，不能选择这条路，需要绕过，continue。

这样，对于大多数的情况，dp[i][child[p][x]] 的值显然应该是等于 dp[i][p] + 1。

可是，如果下一个（第 i + 1 个字符）恰好是我选择的那个 child[p] 呢，比如，我现在已经拥有了 ABB，我决定往 C 走，而原来的情报就是 ABBC，那么就可以直接用原来的情报，不需要修改也可以了。

在状态转移的过程中始终保留 dp[i][j] 的最小值。

int len = strlen(ch + 1);
for (int i = 1; i <= len; i++) {
    for (int p = 0; p < tot; p++) {
        if (sta[p]) {
            // 如果当前节点是一个关键情报，则不能走这条路
            continue;
        }
        for (int x = 0; x < MAXC; x++) {
            if (sta[child[p][x]]) {
                // 如果走下去的方向是关键情报，则需要换一条路
                continue;
            }
            // 到这里，就是一个安全的路，可以做一次状态转移
            // 如果走过去的那个方向，与情报中下一个字符是一样的，就不需要一次修改
            int modify = ch[i] == 'a' + x ? 0 : 1;
            dp[i + 1][child[p][x]] = min(dp[i + 1][child[p][x]], dp[i][p] + modify);
        }
    }
}

最后只需要遍历 dp[len + 1][] 数组中最小值即可。注意动态规划数组的第一个下标是 len + 1 是因为我们需要确保整个情报都不包含关键信息。

由于可能出现无解的情况，而我们又需要记录最小值，所以我们应该把 dp[][] 数组初始化为无穷大，并且在遍历的过程中跳过所有值为无穷大的结点，这样，最后返回的时候就可以直接判断出是不是无解了。

int solve(char *ch) {
    cout << strlen(ch + 1) << endl;

    // 初始化 dp 数组
    memset(dp, 0x3F, sizeof(dp));
    dp[1][0] = 0; // 字符串下标从 1 开始

    int len = strlen(ch + 1);
    for (int i = 1; i <= len; i++) {
        for (int p = 0; p < tot; p++) {
            if (sta[p] || dp[i][p] == INF) {
                // 如果当前节点是一个关键情报，则不能走这条路
                continue;
            }
            for (int x = 0; x < MAXC; x++) {
                if (sta[child[p][x]]) {
                    // 如果走下去的方向是关键情报，则需要换一条路
                    continue;
                }
                // 到这里，就是一个安全的路，可以做一次状态转移
                // 如果走过去的那个方向，与情报中下一个字符是一样的，就不需要一次修改
                int modify = ch[i] == 'A' + x ? 0 : 1;
                dp[i + 1][child[p][x]] = min(dp[i + 1][child[p][x]], dp[i][p] + modify);
            }
        }
    }

    int ans = INF;
    for (int i = 0; i < tot; i++) {
        // 注意是 len + 1
        ans = min(ans, dp[len + 1][i]);
    }
    return ans == INF ? -1 : ans;
}

但是别急，还有一点点小问题。

在使用 AC 自动机进行动态规划的时候，要特别注意，算 fail 要把单词结尾标记传递下来，避免出现某个后缀是另外一个单词的情况。

if (sta[fail[p]]) {
    sta[p] = 1;
}
// 即 sta[p] |= sta[fail[p]]

具体的分析可以参考这一篇文章：https://b.ejq.me/2017/03/01/aczi-dong-ji-yong-yu-dong-tai-gui-hua-shi-de-biao-ji-chuan-di/

#include <bits/stdc++.h>

using namespace std;

const int MAXC = 4; // 这里字符范围只有 A ~ D
const int MAXN = 1007;
const int INF = 0x3F3F3F3F;

int child[MAXN][MAXC], fail[MAXN], sta[MAXN], Q[MAXN];
int tot;
int dp[MAXN][MAXN];

/**
 * AC 自动机
 */
struct AC_Automaton {

    /**
     * 清空
     */
    void clear() {
        memset(child, 255, sizeof(child));
        memset(fail, 0, sizeof(fail));
        tot = 0;
        memset(sta, 0, sizeof(sta));
    }

    /**
     * 插入单词
     * @param ch 单词，该单词下标从 1 开始
     */
    void insert(char *ch) {
        int p = 0, l = strlen(ch + 1);
        for (int i = 1; i <= l; i++) {
            if (child[p][ch[i] - 'A'] == -1) child[p][ch[i] - 'A'] = ++tot;
            p = child[p][ch[i] - 'A'];
        }
        sta[p] = 1; // 以结点 p 的字符串是否存在，由于本题只需要是否存在，设置 true 就好了，像上一题还需要统计个数，可以改为 sta[p]++，表示有多少个
    }

    /**
     * 对插入了单词的前缀树构造失败指针
     */
    void build() {
        int l = 0, r = 0;
        for (int i = 0; i < MAXC; i++)
            if (child[0][i] == -1)
                child[0][i] = 0;
            else
                Q[++r] = child[0][i];
        while (l < r) {
            int p = Q[++l];
            if (sta[fail[p]]) {
                sta[p] = 1;
            }
            for (int i = 0; i < MAXC; i++)
                if (child[p][i] == -1)
                    child[p][i] = child[fail[p]][i];
                else {
                    fail[child[p][i]] = child[fail[p]][i];
                    Q[++r] = child[p][i];
                }
        }
    }

    /**
     *
     * @param ch 字符串，下标从 1 开始
     * @return 最小修改次数
     */
    int solve(char *ch) {

        // 初始化 dp 数组
        memset(dp, 0x3F, sizeof(dp));
        dp[1][0] = 0; // 字符串下标从 1 开始

        int len = strlen(ch + 1);
        for (int i = 1; i <= len; i++) {
            for (int p = 0; p < tot; p++) {
                if (sta[p] || dp[i][p] == INF) {
                    // 如果当前节点是一个关键情报，则不能走这条路
                    continue;
                }
                for (int x = 0; x < MAXC; x++) {
                    if (sta[child[p][x]]) {
                        // 如果走下去的方向是关键情报，则需要换一条路
                        continue;
                    }
                    // 到这里，就是一个安全的路，可以做一次状态转移
                    // 如果走过去的那个方向，与情报中下一个字符是一样的，就不需要一次修改
                    int modify = ch[i] == 'A' + x ? 0 : 1;
                    dp[i + 1][child[p][x]] = min(dp[i + 1][child[p][x]], dp[i][p] + modify);
                }
            }
        }

        int ans = INF;
        for (int i = 0; i < tot; i++) {
            // 注意是 len + 1
            ans = min(ans, dp[len + 1][i]);
        }
        return ans == INF ? -1 : ans;
    }
} T;

int main() {
    // 构造 AC 自动机
    auto ac = new AC_Automaton();
    ac->clear();
    int n;
    scanf("%d", &n);
    // 读入单词，加入前缀树
    char *s = (char *) malloc(sizeof(char) * MAXN);
    for (int i = 0; i < n; i++) {
        // 字符串下标从 1 开始
        scanf("%s", s + 1);
        ac->insert(s);
    }
    // 根据前缀树中的单词构造失败指针，即构造字典
    ac->build();
    // 给定的文章，下标从 1 开始
    char *t = (char *) malloc(sizeof(char) * MAXN);
    scanf("%s", t + 1);
    // 执行操作，输出结果
    printf("%d\n", ac->solve(t));
    return 0;
}