ICPC 4455 Suffix-Replacement Grammars

ICPC 4455 Suffix-Replacement Grammars

[World Finals 2009 - Problem K]

題意：
現給定 N (<=100) 項規則，每項
形式為： X→Y（其中 X 和 Y 等長）
意義是：若字串的後綴為 X，則可花費用 1 ，將後綴替換成 Y。

求由字串 S 轉換至 T 最短路*。（其中 S 和 T 等長）

所有字串長度最多為 20。

[* 即 最小費用，使用 "最短路" 此詞是因為描術更直觀]

---

樣例：
規則：
BC → CD
BC → CA
BCD → CCZ
A → C

S = BBA
T = CCZ

　 BBA
→ BBC (應用 "A → C")
→ BCD (應用 "BC → CD")
→ CCZ (應用 "BCD → CCZ")

Answer: 3

---

題目分析：
直接搜索明顯很容易超時
所以應該先分析將哪些字串納入考慮範圍（視為結點）
然後使用 BFS 或 最短路算法之類...

用上樣例作說明：
當對 "BBC" 應用 "BC → CA"，我們得出 "BCA"
其實 "BCA" 是無所用的

何解？

為了讓 "BCA" 進一步接近 T（即 "BCD"）
我們必需進一步使用長度為 3 的轉換
可是 "BCA" 從沒出現在任何長度為3的變換

那就是說：若果 "BCA" 這後綴沒有在任何規則中出現
則 "BCA" 沒有希望能夠成為轉換過程中的 "踏腳石"

---

算法詳述：
令 DP[LEN][X][Y] 為將字串 X 至 Y 的最短路。
其中 X, Y 長度均為 LEN。

若存在規則 X→Y
則　 DP[LEN][X][Y] = 1
否則 DP[LEN][X][Y] = Infinity

現對於每個固定的 LEN，應用 Floyd-Warshall 最短路算法。

另外：ABCDE→ABXYZ 的最短路
可以由
BCDE→BXYZ 或者
CDE→XYZ
的最短路直接更新

若 X[0]==Y[0] ，則有狀態轉移：
DP[LEN][X][Y] = min( DP[LEN][X][Y], DP[LEN-1][X.substr(1)][Y.substr(1)])

DP 順 LEN 由小至大更新
就可以逐步推移

---

核心算法：
For LEN:=0 to S.length
　　For (X,Y) s.t., X[0]==Y[0]
　　　　DP[LEN][X][Y] = min( DP[LEN][X][Y], DP[LEN-1][X.substr(1)][Y.substr(1)] )
　　EndFor
　　For Rule: X→Y
　　　　If X.length==LEN
　　　　　　DP[LEN][X][Y] = 1
　　　　EndIf
　　EndFor
　Run Floyd-WarShall on DP[LEN]
EndFor

Return DP[S.length][S][T]

---

時間複雜度：
我們只考慮所有出現在字串中的後綴

對於每個固定的 LEN (1 <= LEN <= 20)，
最多有 202 個後綴。

所以時間複雜度最多是 O(20 * 200^3)

---

反直觀：
答案可能超出 32-bit integer