164 - String Computer

Extel推出最新型的電腦 "X9091字串處理機"，主要用途在於密碼學上的應用。該電腦可藉由編程由一組輸入字串產生另一組字串，該電腦用的是精簡指令集晶片(RSIC)，只有三個指令：
1. 刪除(D)特定位置上的字元。
2. 插入(I)一個字元到特定位置。
3. 改變(C)特定位置上的字元。


電腦程式是由機器語言所寫成，且每個指令為固定長度，格式為ZXdd，Z表示刪除(D), 插入(i), 改變(C)其中之一，X表示字元，dd表示兩位數字。程式的結束以一個特殊的結束指令E來表示。


以一個例子來說明，若輸入字串為abcde，我們希望藉由字串的運算得到bcgfe，以下是一個比較簡單的運算方式：


指令      字串
             abcde
Da01     bcde        % a 是必要的
Cg03     bcge
If04       bcgfe
E           bcgef      %程式結束


寫一個程式讀入兩組字串(輸入字串與目標字串)，並找到由輸入字串轉換成目標字串最少所需的指令總數，若有多種可能的解法，只要輸出任一種就可以了。


Input and Output
輸入有許多列，每列有兩個字串，並以一個空白字元分隔。字串長度不會超過20個小寫字元，以#表示輸入結束。


Sample input

abcde bcgfe

#

Sample output

Da01Cg03If04E

原文出處