P7081 [NWRRC 2013] Correcting Curiosity

# [NWRRC2013] Correcting Curiosity “好奇号”是探索火星上盖尔陨石坑的火星车。最近，它在火星土壤中发现了水存在的证据，这将使未来的火星登陆任务变得更加容易。$ $ “好奇号”可以用高达$32 Kbit/s$的速度与地球直接通信 ，但在地球和火星之间传输信号分别平均需要$14$秒和$6$秒。 `你刚刚看到一块石头并踩下了刹车，但你知道火星车已经经过那块石头了` -- 火星车司机Matt Heverly解释道。`所以我们需要规划路线，然后写下一个简单的命令列表：如向前移动一米，左转，拍照等等`. 有时你有必要对一些突发事件做出非常迅速的反应。例如，当相机看到了一些有趣的东西，那么你可能会想改变火星车的路线来拍摄的照片。为此，您需要发送一个形式为 $s/〈string〉/〈replacement〉/g$ . 这将替换所有出现的 $〈string〉,$ 从最左边的开始, 到 $〈replacement〉.$ 更确切地说，如果A是非空字符串，而$B$是字符串, 则要将替换命令$s/A/B/g$应用于字符串$s$，执行以下操作： 在$S$中查找最左边出现的A，这样$S=$SL$+$A$+$SR。 如果没有A，请停止操作。$S$就是答案。 让$R$成为对SR应用$s/A/B/g$的结果。 那么答案是SL$+B+R$。 这就说明: 如果在$S$中有两个重叠的A，那么只替换最左边的一个。例如，将$`s/aba/c/g`$应用于`abababa`会产生`cbc`：在替换第一个`aba `之后，字符串将变为`cbaba `，在此之后只能替换最后一个出现的` aba `。 如果没有替换就使用先前替换的结果。例如，将$`s/a/ab/g`$应用于`a`产生`ab`，将$`s/s/a/ba/g`$应用于`a`产生`ba`。 命令越长，传输它所需的时间就越长。因此，需要你编写一个程序，找到最短的命令，将初始字符串转换为最终字符串。

第一行输入包含初始字符串和最终字符串。这两个字符串都不是空的，并且它们的长度不超过$2000$。字符串仅包含英文字母、空格和标点符号（逗号、冒号、分号和连字符：$'，'，'：'，'；'，'-'）。$给定的字符串不相同。

输出将初始字符串转换为最终字符串并最短的替换命令。如果有多个最短的替换命令，请输出其中任何一个。 ## 样例 #1 ### 样例输入 #1 ``` move left, move right; move up move left, move down, move up ``` ### 样例输出 #1 ``` s/right;/down,/g ``` ## 样例 #2 ### 样例输入 #2 ``` If not found: move x; else move -x If found: move x; else move -x ``` ### 样例输出 #2 ``` s/ not//g ``` ## 样例 #3 ### 样例输入 #3 ``` abababa cbc ``` ### 样例输出 #3 ``` s/aba/c/g ```

时间限制: 2 s, 内存限制: 256 MB.