Виправлення цікавості
Цікавість — це марсохід, який досліджує кратер Гейла на Марсі. Нещодавно він знайшов докази наявності води в марсіанському ґрунті, що полегшить планування майбутніх пілотованих місій.
Цікавість може спілкуватися з Землею безпосередньо зі швидкістю до 32 Кбіт/с, але в середньому потрібно 14 хвилин і 6 секунд для передачі сигналів між Землею та Марсом.
"Ви щойно побачили камінь і натиснули на гальма, але знаєте, що марсохід вже проїжджає цей камінь", — пояснює Метт Хеверлі, водій марсохода. "Тож ми просто плануємо маршрут, потім записуємо список простих текстових команд: рухатися на один метр вперед, повернути ліворуч, зробити фото і так далі".
Іноді необхідно дуже швидко реагувати на деякі несподівані події. Наприклад, якщо камери побачили щось цікаве, то ви можете захотіти змінити маршрут марсохода, щоб зробити додаткове фото. Для цього ви надсилаєте команду заміни у формі s///g. Це замінює всі входження, починаючи з крайнього лівого, на .
Більш формально, якщо A — це непорожній рядок, а B — рядок, то для застосування команди заміни s/A/B/g до рядка S, слід виконати наступне:
Знайти крайнє ліве входження A в S, таке що S = SL + A + SR.
Якщо такого входження немає, зупинитися. Тоді, S є відповіддю.
Нехай R буде результатом застосування s/A/B/g до SR.
Відповідь — це SL + B + R.
Це означає, що:
Якщо є два перекриваючі входження A в S, замінюється лише крайнє ліве. Наприклад, застосування "s/aba/c/g" до "abababa" дає "cbc": після заміни першого входження "aba" рядок перетворюється на "cbaba", і лише останнє входження "aba" може бути замінено після цього.
Жодна заміна не використовує результати попередніх замін. Наприклад, застосування "s/a/ab/g" до "a" дає "ab", застосування "s/a/ba/g" до "a" дає "ba".
Ви знаєте, що чим довша команда, тим більше часу потрібно для її передачі. Тому вам потрібно написати програму, яка знаходить найкоротшу команду, що перетворює початковий рядок у кінцевий рядок.
Вхідні дані
Перша строка містить початковий і кінцевий рядки. Обидва рядки непорожні, і їх довжина не перевищує 2000 символів. Рядки містять лише англійські літери, пробіли та знаки пунктуації (коми, двокрапки, крапки з комою та дефіси: ',', ':', ';', '-'). Дані рядки не рівні.
Вихідні дані
Виведіть команду заміни, яка перетворює початковий рядок у кінцевий рядок і має мінімальну довжину. Якщо існує декілька найкоротших команд заміни, виведіть будь-яку з них.