Alt sətirlər

1977-ci ildə Phi-X174 fağının sekvenləşdirilməsindən bəri, minlərlə orqanizmin DNT ardıcıllıqları deşifrə edilmiş və məlumat bazalarında saxlanılmışdır. Bu ardıcıllıq məlumatları polipeptidləri (zülallar), RNT genlərini, tənzimləyici sahələri, struktur motivləri və təkrarlanan ardıcıllıqları müəyyən etmək üçün təhlil edilir. Eyni və ya müxtəlif növlər daxilində genlərin müqayisəsi zülal funksiyalarında oxşarlıqları və ya növlər arasındakı əlaqələri göstərə bilər (molekulyar sistematikadan istifadə etməklə filogenetik ağacların qurulması üçün). Məlumatların sürətlə artması ilə əl ilə DNT ardıcıllıqlarını təhlil etmək artıq mümkün deyil. Bu günlərdə BLAST kimi kompüter proqramları gündəlik olaraq 260 000-dən çox orqanizmdən, 190 milyarddan çox nukleotid ehtiva edən ardıcıllıqları axtarmaq üçün istifadə olunur. Bu proqramlar DNT ardıcıllığındakı mutasiyaları (əvəzlənmiş, silinmiş və ya əlavə olunmuş əsaslar) kompensasiya edə və dəqiq uyğun gəlməyən, lakin əlaqəli ardıcıllıqları müəyyən edə bilər. Bu cür uyğunlaşdırmanın bir variantı sekvenləşdirmənin özündə də istifadə olunur. Məsələn, ilk bakterial genom olan Haemophilus influenzae-nin ardıcıllığının çıxarılmasında istifadə olunan "shotgun sekvenləşdirmə" üsulu bütün xromosomu deyil, minlərlə kiçik DNT fraqmentinin ($35$ ilə $900$ nukleotid uzunluğunda, texnologiyadan asılı olaraq) ardıcıllığını yaradır. Bu fraqmentlərin ucları üst-üstə düşür və uyğun şəkildə düzüləndə tam genomun bərpasına imkan verir. Shotgun sekvenləşdirmə tez bir zamanda ardıcıllıq məlumatı əldə etməyə imkan verir, lakin böyük genomlar üçün fraqmentlərin yığılması olduqca çətin bir tapşırıqdır. İnsan genomu kimi böyük genomların yığılması çoxsaylı prosessorlu, böyük yaddaşa malik kompüterlərdə belə bir neçə gün CPU vaxtı ala bilər və əldə olunan ardıcıllıq adətən sonradan doldurulmalı olan çoxlu boşluqlarla müşayiət olunur. Günümüzdə demək olar ki, bütün genomların sekvenləşdirilməsində bu üsuldan istifadə edilir və genom yığma alqoritmləri bioinformatikanın əsas tədqiqat sahələrindən biridir.

Giriş məlumatları

Giriş $n$ sətirdən ibarətdir, hər biri uzunluğu $l$ olan bir sətrdir. Hər bir sətir yalnız ingilis əlifbası hərflərindən [A-Za-z] (2 \le n \le 100\ 000, 2 \le l \le 100\ 000) ibarətdir. Böyük və kiçik hərflər fərqli hesab olunur. Testlərdə giriş və çıxış xərclərini azaltmaq üçün n \times l \le 5 \times 1\ 024 \times 1\ 024 məhdudiyyəti yerinə yetirilir.

Çıxış məlumatları

Uzunluğu l + n - 1 olan bir sətir çıxarın ki, verilmiş bütün sətirlər onun müxtəlif mövqelərindən başlayan alt sətrləri olsun. Belə bir sətirin mövcudluğu təmin olunur. Bir neçə cavab mümkündürsə, istənilən birini çıxarın.