如何通过反复从字符串

Question

这个问题出现在程序设计大赛去除一些特定单词的所有出现的最小化字符串的长度，我们仍然不知道如何解决它。

问： 给定的线S和串L1名单，我们希望保持删除子，可能是在L的所有出现，我们必须尽量减少形成最终的字符串的长度。另请注意，删除字符串可能会启动更多清除。

例如，

1. S = ccdedefcde，L = {} CDE 然后回答= 1。因为我们可以通过ccdedefcde减少的S - > cdefcde - > fcde - > F。
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

请提出一个高效的算法，可以解决这个问题。

Answer 1

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

现在我们只需要用上下文无关文法来正式确定这个问题。开始符号为A（通常为S，但已采用），并带有以下产品。

A -> N  (weight 0) 
A -> A C N (weight 0) 

我会尽快解释N。如果N和C是终端，则A将接受常规语言N (C N)*。非终结符C匹配单个终端（字符）。

C -> a (weight 1) 
C -> b (weight 1) 
C -> c (weight 1) 
... 

非终结N匹配字符串是可空，即，可以通过删除字符串L被减小为空字符串字符串。基本情况很明显。

N ->    (weight 0) 

我们还为每个元素L生产。例如，当L = {mca, pa}时，我们有以下产品。

N -> N m N c N a N (weight 0) 
N -> N p N a N  (weight 0) 

希望很明显如何构造迭代清除并解析，其中，所述解析重量等于剩余字符串的长度之间的一对一对应。

Answer 2

注：这不是一个最佳的解决方案，因为它不针对例如S=ABAABABAA, L={ABA}

工作算法

RECURSIVE_FUNCTION (STRING STR, STRING PATTERN) : 

1. STRING LEFT = STR.SUBSTR (0, STR.FIND(PATTERN)) 

2. STRING RIGHT = STR.SUBSTR(STR.FIND(PATTERN), STR.LENGTH) 

3. IF (RIGHT is empty) THEN RETURN LEFT 

4. STRING FIN = RECUR(LEFT) + RECUR(RIGHT) 

5. RETURN RECUR(FIN) 

功能SUBSTR(A,B)将返回字符串的子串，从包含索引A到包含索引B

操作A + B是串A的级联和B

函数RECUR(A)呼叫相同的功能，也称为复发

---

实施例：ccdedefcde

首先将跳转下来RECUR(LEFT) + RECUR(RIGHT)：

c[cde]defcde 
/ \ 
c  def[cde] 
    /
     def 

那么它将RECUR(FIN)在合并：

cdef* 
/\ 
c def 
    /
    def 

*会复发做以下是MERGE完成前：

[cde]f 
     \ 
     f 

终于ROOT调用返回f