这个问题出现在编程竞赛中，我们仍然不知道如何解决。
问题：给定一个字符串S和一个字符串L的列表，我们要继续删除可能在L中出现的所有子字符串。而且，我们必须最小化形成的最终字符串的长度。另请注意，删除字符串可能会启动更多删除操作。
例如，
S的最大长度可以是50，列表L的最大长度可以是50。
我的方法是一种基本的递归遍历，在该遍历中，我返回通过删除不同的子字符串可以获得的最小长度。不幸的是，这种递归方法在最坏的情况下会超时，因为我们每个步骤都有50个选项，递归深度为50。
请提出一种可以解决此问题的有效算法。
这是产生最佳结果的多项式时间算法。因为对我来说方便，所以我将使用多项式时间CYK算法作为子例程，特别是扩展，该扩展根据具有加权乘积的无上下文语法来计算字符串的最小权重解析。
现在，我们只需要使用无上下文语法来规范此问题。起始符号是A（通常是S，但是已经被使用），并带有以下形式。
A
S
A -> N (weight 0) A -> A C N (weight 0)
我会尽快解释N。如果N和C是终端，A则将接受常规语言N (C N)*。非C终端匹配单个终端（字符）。
N
C
N (C N)*
C -> a (weight 1) C -> b (weight 1) C -> c (weight 1) ...
非终结符N匹配可为 空的 字符串，即，可以通过删除中的字符串将其还原为空字符串L。基本情况是显而易见的。
L
N -> (weight 0)
我们还为的每个元素都有一个生产L。L = {mca, pa}例如，当时，我们具有以下作品。
L = {mca, pa}
N -> N m N c N a N (weight 0) N -> N p N a N (weight 0)
我希望很清楚如何在迭代删除和解析之间构造一对一的对应关系，其中解析权重等于剩余字符串的长度。
