Задача №1997. Первоапрельская шутка
Андрей работает в серьёзном книжном издательстве. Однако даже самые серьёзные компании могут позволить себе немного пошутить на 1 апреля.
В связи с этим, начальство поручило Андрею немного подредактировать название готовящейся к выпуску книги, состоящее из двух слов. Он решил сделать это следующим образом: взять какую- нибудь непустую подстроку первого слова, почти такую же подстроку второго слова и поменять их местами. Две строки назовём почти одинаковыми, если они имеют одинаковую длину и количество позиций, на которых в этих строках стоят разные буквы, не превышает заранее вычисленного Андреем числа \(K\). (Например, слова «good» и «book» не совпадают в двух позициях — первой и последней.)
Также Андрей решил, что для большего эффекта менять местами следует куски как можно большей длины. Эту самую длину Андрей и попросил Вас найти.
В первых двух строках входного файла содержатся соответственно непустые строки \(s\) и \(t\), состоящие из строчных латинских букв,— первое и второе слова в названии книги (\(|s|,|t| \le6\,000\)). В третьей строке находится целое число \(K\) (\(0\le K \le6\,000\)).
Выведите единственное целое число: 0, если решения не существует, и максимальную длину кусков, которые можно поменять местами, в противном случае.
Комментарий к примеру тестов.
Поменять местами можно либо подстроки «ood» и «ook», либо «goo» и «boo».
good book 1
3