DNA Subsequences#3527

DNA Subsequences

2 saniyə

256 meqabayt

Çox asan

Tomas, DNT ardıcıllıqları üzərində çalışan bir kompüter alimi, verilmiş cüt sətrlərin ən böyük ortaq altardıcıllığını tapmalıdır.

Hərflərdən ibarət $Σ$ əlifbası və $w = a_{1} a_{2} \dots a_{r}$ w = a_1 a_2 \ldots a_r sözü verilsin, burada $a_{i} \in Σ$ a_i \in \Sigma hər $i = 1, 2, \dots, r$ i = 1, 2, \ldots, r üçün. $w$ -nun altardıcıllığı $x = a_{i_{1}} a_{i_{2}} \dots a_{i_{s}}$ x = a_{i_1} a_{i_2} \ldots a_{i_s} sözüdür, burada $1 \leq i_{1} < i_{2} < \dots < i_{s} \leq r$ 1 \leq i_1 < i_2 < \ldots < i_s \leq r. $x$ altardıcıllığı $w$ sözünün segmentidir, əgər $i_{j + 1} = i_{j} + 1$ i_{j+1} = i_j + 1 hər $j = 1, 2, \dots, s - 1$ j = 1, 2, \ldots, s-1 üçün. Məsələn, lovely sözü lovely-nin segmentidir, halbuki loly sözü lovely-nin altardıcıllığıdır, ancaq segmenti deyil.

Bir söz iki $w_{1}$ w_1 və $w_{2}$ w_2 sözünün ortaq altardıcıllığıdırsa, deməkdir ki, o, hər ikisinin də altardıcıllığıdır. $w_{1}$ w_1 və $w_{2}$ w_2-nin ən uzun ortaq altardıcıllığı, hər iki sözün ən uzun ümumi altardıcıllığıdır. Məsələn, $w_{1} = lovxxelyxxxxx$ w_1 = \texttt{lovxxelyxxxxx} və $w_{2} = xxxxxxxlovely$ w_2 = \texttt{xxxxxxxlovely} sözlərini nəzərə alaq. $w_{3} = lovely$ w_3 = \texttt{lovely} və $w_{4} = xxxxxxx$ w_4 = \texttt{xxxxxxx} sözləri, ikincisi $7$ uzunluğunda olmaqla, $w_{1}$ w_1 və $w_{2}$ w_2-nin ortaq altardıcıllıqlarıdır. Əslində, $w_{4}$ w_4 onların ən uzun ortaq altardıcıllığıdır. Qeyd edin ki, uzunluğu sıfır olan boş sətr də həmişə ortaq altardıcıllıq sayılır, lakin ən uzun olmaya da bilər.

Tomasın tapşırığında əlavə tələb var: tapılacaq ümumi altardıcıllıq yalnız hər iki sətrdə ən azı $K$ uzunluqda olan ortaq ardıcıl seqmentlərdən təşkil olunmalıdır. Məsələn, əgər $K = 3$ K=3-dürsə, $w_{3} = lovely$ w_3 = \texttt{lovely} $w_{1}$ w_1 və $w_{2}$ w_2-nin mümkün ortaq altardıcıllığıdır, amma $w_{4} = xxxxxxx$ w_4 = \texttt{xxxxxxx}, uzunluğu $7$ olsa belə və hər iki sətrin ortaq altardıcıllığıdırsa da, uyğun deyil. Siz Tomasa kömək edə bilərsinizmi?

Giriş

Girişdə bir neçə test halı verilir. Hər test halının birinci sətrində $K$ ( $1 \leq K \leq 100$ 1 \leq K \leq 100) tam ədədi verilir, $K$ - minimal seqment uzunluğudur. Sonrakı iki sətrdə ingilis əlifbasının kiçik hərflərindən ( $26$ hərf) ibarət iki sətir verilir. Hər bir sətrin uzunluğu $l$ üçün $1 \leq l \leq 1 0^{3}$ 1 \leq l \leq 10^3. Girişin heç bir sətrində boşluq yoxdur. Girişin sonu tərkibində tək bir sıfır olan sətrlə göstərilir.

Çıxış

Girişdəki hər test halı üçün, hər iki sətrdə ardıcıl olaraq ən azı $K$ uzunluqda ortaq seqmentlərdən yığılan ən uzun ümumi altardıcıllığın uzunluğunu verin. Belə ardıcıllığın uzunluğu sıfırdan böyük deyilsə, $0$ çap edin.

Nümunələr

Nümunə 1