Дана строка s, состоящая из больших латинских букв. Обозначим ее текущую длину как |s|. За один ход разрешается применить к ней одну из следующих операций:
Ваша задача — найти, за какое наименьшее количество ходов можно получить из строки s строку t. Так же требуется найти последовательность действий, приводящую к нужному результату.
В первой строке записана s, во второй строке записана t. Строки состоят только из больших латинских букв, их длины — положительные числа от 1 до 1000.
В первую строку выведите количество ходов k в найденной последовательности операций. Это число должно быть наименьшим возможным. Далее выведите k строк по одной операции в каждой. Операции выводите в описанном выше формате. Если решений несколько, выведите любое.
ABA ABBBA
2 INSERT 3 B INSERT 4 B
ACCEPTED WRONGANSWER
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач