← 返回题目列表

Codeforces · 56/D

D. 更改字符串

中文机器翻译题面 查看原题

有一个字符串 s,由大写拉丁字母组成。我们将其当前长度表示为|s|。在一次移动过程中,允许对其应用以下操作之一:

- INSERT pos ch — 在字符串 s 的 pos 位置插入字母 ch (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z)。字母 ch 成为字符串 s 的第 pos 个符号,此时字母移到一边并且字符串的长度增加 1。
- DELETE pos — 从字符串 s 中删除第一个字符 pos (1 ≤ pos ≤ |s|)。此时字母会移动到一起,并且字符串的长度减少 1。
- REPLACE pos ch — 将 s 行 pos 位置的字母替换为 ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z)。此时字符串的长度不会改变。

你的任务是找出从 s 字符串中得到 t 字符串所需的最小移动次数。您还应该找到导致所需结果的操作顺序。

输入

第一行包含 s,第二行包含 t。这些行仅由大写拉丁字母组成,其长度为 1 到 1000 之间的正数。

输出

在第一行中打印给定操作序列中的移动次数 k。该数量应该是尽可能少的数量。然后打印 k 行,每行包含一个操作。按照上述格式打印操作。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

ABA
ABBBA

输出 #1

2
INSERT 3 B
INSERT 4 B

输入 #2

ACCEPTED
WRONGANSWER

输出 #2

10
REPLACE 1 W
REPLACE 2 R
REPLACE 3 O
REPLACE 4 N
REPLACE 5 G
REPLACE 6 A
INSERT 7 N
INSERT 8 S
INSERT 9 W
REPLACE 11 R