Неточний пошук
Задача пошуку заданого підрядка у тексті має незаперечне значення і її розв'язання реалізовано у більшості мов програмування у вигляді функціональності стандартної бібліотеки. Проте, часто необхідно розв'язувати задачу неточного пошуку. Назвемо відстанню між двома рядками a та b найменшу кількість операцій, які необхідні для того, щоб рядок a перетворити у рядок b. Дозволені операції: заміна довільноого символу довільним іншим, вставка довільного символу у довільну позицію у рядку і видалення довільного символу. Наприклад, відстань між рядками "кіт" і "кінь" дорівнює 2. Ваша задача у заданому тексті знайти підрядок, який має відстань до заданого не більшу d.
Вхідні дані
У першому рядку записано рядок у якому слід здійснювати пошук. Довжина рядка не менше 1 символу і не більше 2·10^6. Далі міститься рядок, який містить зразок пошуку. Його довжина не менше 1 символу і не більше 50 символів. Задані рядки містять рядкові та прописні літери латинського алфавіту і цифри. Останній рядок містить ціле число d (0 ≤ d ≤ 50) – найбільшу відстань між зразком пошуку та шуканим підрядком.
Вихідні дані
Виведіть два цілих числа start, length, де start – позиція першого символу знайденого підрядка, а length – його довжина. Нумерація символів у рядку починається з нуля. Якщо розв'язків декілька, виведіть довільний.