
计蒜客 – 情报加密
蒜头君是我军的情报专家,现在我军有一份重要情报要发送出去,这是一份特别重要的情报,一旦被敌军截获,里面有一些重要的片段会暴露我们的身份,所以蒜头君需要改变一些字符,这样即使敌军截获了我们的情报,也无法获得正确信息。
比如,情报中如果包含 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; }