Processing math: 100%

Задача C. Неточные подстроки

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Будем говорить, что строки a и b имеют k различий, если длины этих строк одинаковы, а символы в позициях с одинаковыми номерами совпадают все, кроме k штук. Например, строки ABABAC и BBABAB имеют 2 различия.

По данной строке S длиной N символов и числу k требуется найти две подстроки одинаковой длины, начинающиеся с различных позиций, и имеющие не более k различий.

Формат входного файла

Входной файл содержит в первой строке целое число k, в во второй — строку S.

Формат выходного файла

Выходной файл должен содержать целое число — длину самой длинной найденной подстроки, либо 0 (ноль), если решения не существует.

Ограничения

Строка S состоит из заглавных латинских букв.

0kN1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 
A
0
2
2
ABCACB
3

0.065s 0.008s 13