Редактирование расстояния еще раз
Редактирование расстояния еще раз
Вы когда-нибудь слышали о проблеме расстояния редактирования? По двум строкам из английских букв необходимо найти минимальное количество операций, необходимых для преобразования первой строки во вторую. Одной операцией может быть:
- вставка символа в последовательность в любом месте,
- удаление любого символа из последовательности,
- замена одного символа другим.
Все в нашем университете очень любят эту задачу, может быть, даже слишком, поэтому мы решили создать задачу попроще! Вам даны две строки s = s1
...sn
, t = t1
...tm
и целое число k. Определите, меньше или равно k расстояние редактирования между строками. Если это так, вас также просят указать любую последовательность минимально возможного количества операций для преобразования первой строки во вторую.
Входные данные
Первая строка содержит количество тестов z (1 ≤ z ≤ 100). Далее следуют описания тестов.
Первая строка каждого теста содержит три целых числа n, m, k (1 ≤ n, m ≤ 106
, 0 ≤ k ≤ 1000) — длины строк и параметр из описания задачи.
Во второй строке находится строка длины n, состоящая из строчных латинских букв - строка s из описания задачи.
В третьей строке находится строка длины m, состоящая из строчных латинских букв - строка t из описания задачи.
Суммарная длина всех строк во всех тестах не превышает 107
.
Выходные данные
Для каждого теста, если расстояние редактирования больше k, выведите одну строку, содержащую слово "NO". В противном случае первая строка должна содержать слово "YES", а следующие строки должны описывать ответ следующим образом:
Во второй строке выведите минимальное количество r операций, необходимых для преобразования s в t. В следующих r строках выведите операции, по одной в строке.
- Чтобы вставить символ c в последовательность размером w в позицию p (1 ≤ p ≤ w + 1), выведите INSERT p c.
- Чтобы удалить символ из последовательности размера w в позиции p (1 ≤ p ≤ w), выведите DELETE p .
- Чтобы заменить символ в последовательности размером w в позиции p (1 ≤ p ≤ w) символом c, выведите REPLACE p c.
2 3 4 3 kot plot 5 7 3 zycie porazka
YES 2 REPLACE 1 l INSERT 1 p NO