如何通過反覆從字符串

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