Послідовності ДНК#3527

Послідовності ДНК

2 секунди

256 мегабайтів

Дуже легка

Томас, фахівець з комп'ютерних наук, який працює з послідовностями ДНК, повинен знайти найдовшу спільну підпослідовність для вказаних пар рядків.

Розглянемо алфавіт $Σ$ з букв і слово $w = a_{1} a_{2} \dots a_{r}$ w = a_1 a_2 \ldots a_r, де $a_{i} \in Σ$ a_i \in \Sigma для $i = 1, 2, \dots, r$ i = 1, 2, \ldots, r. Підпослідовністю слова $w$ називається слово $x = a_{i_{1}} a_{i_{2}} \dots a_{i_{s}}$ x = a_{i_1} a_{i_2} \ldots a_{i_s} таке, що $1 \leq i_{1} < i_{2} < \dots < i_{s} \leq r$ 1 \leq i_1 < i_2 < \ldots < i_s \leq r. Підпослідовність $x$ є сегментом слова $w$ , якщо $i_{j + 1} = i_{j} + 1$ i_{j+1} = i_j + 1 для $j = 1, 2, \dots, s - 1$ j = 1, 2, \ldots, s-1. Наприклад, слово lovely є сегментом слова lovely, тоді як слово loly є підпослідовністю слова lovely, але не сегментом.

Слово називається спільною підпослідовністю двох слів $w_{1}$ w_1 і $w_{2}$ w_2, якщо воно є підпослідовністю кожного з цих слів. Найдовша спільна підпослідовність $w_{1}$ w_1 і $w_{2}$ w_2 — це спільна підпослідовність $w_{1}$ w_1 і $w_{2}$ w_2, яка має найбільшу можливу довжину. Наприклад, розглянемо слова $w_{1} = lovxxelyxxxxx$ w_1 = \texttt{lovxxelyxxxxx} і $w_{2} = xxxxxxxlovely$ w_2 = \texttt{xxxxxxxlovely}. Слова $w_{3} = lovely$ w_3 = \texttt{lovely} і $w_{4} = xxxxxxx$ w_4 = \texttt{xxxxxxx}, останнє з яких має довжину $7$ , є спільними підпослідовностями $w_{1}$ w_1 і $w_{2}$ w_2. Насправді, $w_{4}$ w_4 — їхня найдовша спільна підпослідовність. Зауважте, що порожній рядок довжини нуль завжди є спільною підпослідовністю, хоча й не обов'язково найдовшою.

У випадку Томаса є додаткова вимога: спільна підпослідовність повинна складатися із спільних сегментів довжиною не менше $K$ . Наприклад, якщо $K = 3$ K = 3, то $w_{3} = lovely$ w_3 = \texttt{lovely} є припустимою спільною підпослідовністю $w_{1}$ w_1 і $w_{2}$ w_2, тоді як $w_{4} = xxxxxxx$ w_4 = \texttt{xxxxxxx}, хоча має довжину $7$ і теж є спільною підпослідовністю, не підходить. Чи можете допомогти Томасу?

Вхідні дані

Вхід містить кілька тестових випадків. Перший рядок тесту містить ціле число $K$ ( $1 \leq K \leq 100$ 1 \leq K \leq 100), мінімальну довжину спільних сегментів. Наступні два рядки містять кожна по рядку з малих літер англійського алфавіту ( $26$ букв). Довжина $l$ кожного рядка задовольняє $1 \leq l \leq 1 0^{3}$ 1 \leq l \leq 10^3. Жоден рядок входу не містить пробілів. Кінець входу позначається рядком з одного нуля.

Вихідні дані

Для кожного тестового випадку виведіть один рядок, що містить довжину найдовшої спільної підпослідовності, складеної з послідовних спільних сегментів довжиною не менше $K$ з обох рядків. Якщо такої підпослідовності довжиною більше нуля не існує, виведіть $0$ .

Приклади

Приклад 1