CF1163D Mysterious Code

在一次普通的森林散步中，Katie 偶然发现了一段神秘的代码！然而，这段神秘代码中有些字符无法辨认。她将这段代码记录为一个字符串 $c$，其中包含小写英文字母和星号（“\*”），每个星号表示一个无法辨认的字符。Katie 对她的发现感到非常兴奋，决定通过将每个星号替换为任意小写英文字母（不同的星号可以替换为不同的字母）来恢复这些无法辨认的字符。 Katie 有一个喜欢的字符串 $s$ 和一个不太喜欢的字符串 $t$。她希望恢复出的神秘代码中，$s$ 出现的次数尽可能多，而 $t$ 出现的次数尽可能少。形式化地，设 $f(x, y)$ 表示字符串 $y$ 在字符串 $x$ 中出现的次数（例如，$f(aababa, ab) = 2$）。Katie 想要恢复出一个符合原始 $c$ 的字符串 $c'$，使得 $f(c', s) - f(c', t)$ 的值最大。但 Katie 并不擅长恢复代码，所以她希望你来帮助她。

第一行包含字符串 $c$（$1 \leq |c| \leq 1000$）——神秘代码。保证 $c$ 只包含小写英文字母和星号“\*”。 第二行和第三行分别包含字符串 $s$ 和 $t$（$1 \leq |s|, |t| \leq 50$，$s \neq t$）。保证 $s$ 和 $t$ 只包含小写英文字母。

输出一个整数——恢复后的代码中 $f(c', s) - f(c', t)$ 的最大可能值。

在第一个样例中，若 $c'$ 为 "katie"，则 $f(c', s) = 1$，$f(c', t) = 0$，因此 $f(c', s) - f(c', t) = 1$，这是最大的可能值。 在第二个样例中，唯一符合给定 $c$ 的 $c'$ 是 "caat"。此时 $f(c', s) - f(c', t) = 1 - 2 = -1$。 在第三个样例中，有多种方式恢复代码使得 $f(c', s) - f(c', t)$ 达到最大，例如 "aaa"、"aac" 或 "zaz"。这些恢复后的代码 $f(c', s) - f(c', t) = 0$。 在第四个样例中，最优的恢复代码 $c'$ 是 "ccc"。此时 $f(c', s) - f(c', t) = 2$。 由 ChatGPT 4.1 翻译