Последовательности ДНК
Томас, специалист по компьютерным наукам, работающий с последовательностями ДНК, должен вычислить наибольшие общие подпоследовательности для заданных пар строк. Рассмотрим алфавит Σ и слово w=a_1a_2 …a_r, где a_i ∈ Σ для i = 1, 2, …, r. Подпоследовательность w — это слово x=a_i1a_i2 …a_is, такое что 1 ≤ i_1 < i_2 < … < i_s ≤ r. Подпоследовательность x является сегментом w, если i_{j+1}=i_j + 1 для j = 1, 2, …, s-1. Например, слово является сегментом слова, тогда как слово является подпоследовательностью, но не сегментом.
Слово является общей подпоследовательностью двух слов w_1 и w_2, если оно является подпоследовательностью каждого из этих слов. Наибольшая общая подпоследовательность w_1 и w_2 — это общая подпоследовательность w_1 и w_2, имеющая наибольшую возможную длину. Например, рассмотрим слова w_1= и w_2=. Слова w_3= и w_4=, последнее из которых имеет длину 7, являются общими подпоследовательностями w_1 и w_2. На самом деле, w_4 является их наибольшей общей подпоследовательностью. Обратите внимание, что пустое слово длиной ноль всегда является общей подпоследовательностью, хотя и не обязательно наибольшей.
В случае Томаса есть дополнительное требование: подпоследовательность должна быть сформирована из общих сегментов длиной K или более. Например, если Томас решает, что K=3, то он считает допустимой общей подпоследовательностью, тогда как , которая имеет длину 7 и также является общей подпоследовательностью, не является допустимой. Можете помочь Томасу?
Входные данные
Вход содержит несколько тестовых случаев. Первая строка тестового случая содержит целое число K, представляющее минимальную длину общих сегментов, где 1 ≤ K ≤ 100. Следующие две строки содержат каждую строку из строчных букв обычного алфавита из 26 букв. Длина l каждой строки удовлетворяет неравенству 1 ≤ l ≤ 10^3. На любой строке входа нет пробелов. Конец входа обозначается строкой, содержащей ноль.
Выходные данные
Для каждого тестового случая на входе ваша программа должна вывести одну строку, содержащую длину наибольшей подпоследовательности, сформированной из последовательных сегментов длиной не менее K из обеих строк. Если такой общей подпоследовательности длиной больше нуля не существует, то должно быть выведено 0.