算法|题解

计蒜客 – 情报加密

jxtxzzw · 3月20日 · 2020年 · · · · · 223次已读

计蒜客 – 情报加密

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

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

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

输入格式

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

接下来 $n$ 行,每行一个长度不超过 $20$ 的字符串,由 ABCD构成。

最后一行,一个长度不超过 $10^3$ 的字符串是,由 ABCD 构成。

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 + 1p 只能转移到 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;
}

说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
  订阅评论动态  
提醒