Послідовності ДНК
Томас, фахівець з комп'ютерних наук, який працює з послідовностями ДНК, має завдання обчислити найбільші спільні підпослідовності для заданих пар рядків. Розглянемо алфавіт Σ і слово 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.