如何通过反复从字符串中删除所有出现的某些指定单词来最小化字符串的长度

Question

这个问题出现在编程竞赛中，我们仍然不知道如何解决。

问题：给定一个字符串S和一个字符串L的列表，我们希望继续删除可能在L中出现的所有子字符串。而且，我们必须最小化形成的最终字符串的长度。另请注意，删除字符串可能会启动更多删除操作。

例如

1. S = ccdedefcde，L = {cde}然后答案=1。因为我们可以通过ccdedefcde-> cdefcde-> fcde-> f来减少S。
2. S = aabaab，L = {aa，bb}然后答案= 0，因为还原可以通过aabaab-> aabb-> aa->'空字符串']进行
3. S = acmmcacamapapc，L = {mca，pa}然后答案= 6，因为还原可以通过acmmcacamapapc-> acmcamapapc-> acmapapc-> acmapc进行。

S的最大长度可以为50，列表L的最大长度可以为50。

我的方法是一种基本的递归遍历，在该遍历中，我返回通过删除不同的子字符串可以获得的最小长度。不幸的是，这种递归方法在最坏的情况下会超时，因为我们每个步骤都有50个选项，递归深度为50。

请提出一种可以解决此问题的有效算法。

[这个问题出现在编程竞赛中，我们仍然不知道如何解决。问题：给定一个字符串S和一个字符串L的列表，我们希望继续删除所有出现的子字符串...

Answer 1

这里是产生最佳结果的多项式时间算法。因为对我来说方便，所以我将使用多项式时间CYK algorithm作为子例程，特别是用于根据具有加权乘积的无上下文语法计算字符串的最小权重解析的扩展。

现在，我们只需要使用上下文无关的语法来形式化此问题。起始符号为A（通常为S，但已被采用），并带有以下结果。

Answer 2

注意：这不是最佳解决方案，因为它不适用于示例

Answer 3

此代码将提供最佳解决方案