string - 从字符串 'A' 中删除最少的字母以删除字符串 'B' 的所有实例

Question

如果我们有长度为 N 的字符串 A 和长度为 M 的字符串 B，其中 M < N，我能否快速计算出我必须删除的最少字母数来自字符串 A 以便字符串 B 不会作为 A 中的子字符串出现？

如果我们的字符串长度很小，这个问题很容易暴力破解:你只需迭代一个从 0 到 2^N 的位掩码，看看是否 B 作为 A 子序列中的子字符串出现。然而，当 N 可以达到 10,000，M 可以达到 1,000 时，这个算法显然很快就会崩溃。有更快的方法吗？

示例:A=ababaa B=aba。 Answer=1。删除 A 中的第二个 a 将导致 abbaa，其中不包含 B。

编辑: 用户名发布了一个很好的反例:aabcc 和 abc。我们要删除单个 b，因为删除任何 a 或 c 都会创建字符串 abc 的另一个实例.

Answer 1

用动态规划求解。让 dp[i][j] 最小运算符使 A[0...i-1] 具有 B[0...j-1] 的后缀以及 A[0...i] 没有' t 包含 B，dp[i][j] = Infinite 来索引运算符是不可能的。然后

if(A[i-1]=B[i-1]) 
   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])    
else dp[i][j]=dp[i-1][j]`,

return min(A[N][0],A[N][1],...,A[N][M-1]);`