Alt sətirlər
1977-ci ildə Phi-X174 faqının sekvenləşdirilməsindən bəri, getdikcə daha çox orqanizmin DNT ardıcıllıqları deşifrə edilmiş və məlumat bazalarında saxlanılmışdır. Bu məlumatlar zülalların və tənzimləyici sahələrin ardıcıllığını müəyyən etmək üçün istifadə olunur. Eyni və ya müxtəlif növlər daxilində genlərin müqayisəsi zülal funksiyalarının oxşarlığını və ya növlər arasındakı əlaqələri göstərə bilər (beləliklə, filogenetik ağaclar tərtib edilə bilər). Məlumatların artması ilə artıq ardıcıllıqları əl ilə təhlil etmək mümkün deyil. Bu günlərdə milyardlarla nukleotid cütündən ibarət olan minlərlə orqanizmin genomlarını axtarmaq üçün kompüter proqramları istifadə olunur. Proqramlar müxtəlif növlərin genomlarında oxşar DNT ardıcıllıqlarını dəqiq şəkildə uyğunlaşdıra (sıralaya) bilər; tez-tez belə ardıcıllıqlar oxşar funksiyaları daşıyır və fərqlər ayrı-ayrı nukleotidlərin əvəzlənməsi, nukleotidlərin daxil edilməsi və onların "düşməsi" (delesiya) kimi kiçik mutasiyalar nəticəsində yaranır. Belə uyğunlaşmanın bir variantı sekvenləşdirmə prosesində tətbiq edilir. "Shotgun sekvenləşdirmə" adlanan texnika (məsələn, Genetik Tədqiqatlar İnstitutu tərəfindən Haemophilus influenzae-nin ilk bakterial genomunun sekvenləşdirilməsi üçün istifadə edilmişdir) tam nukleotid ardıcıllığı əvəzinə qısa DNT fraqmentlərinin ardıcıllığını verir (hər biri təxminən 600-800 nukleotid uzunluğunda). Fraqmentlərin ucları bir-birinə üst-üstə düşür və düzgün birləşdirildikdə tam genomu verir. Bu metod sekvenləşdirmə nəticələrini tez verir, lakin fraqmentlərin yığılması böyük genomlar üçün olduqca çətin bir vəzifə ola bilər. İnsan genomunun deşifrələnməsi layihəsində yığılma bir neçə ay kompüter vaxtı aldı. İndi bu metod demək olar ki, bütün genomlar üçün tətbiq edilir və genom yığma alqoritmləri bu gün bioloji informatikanın ən kəskin problemlərindən biridir.
Giriş məlumatları
n sətirdə eyni uzunluqda l olan n sətir verilir. Bu sətirlər yalnız ingilis əlifbasının simvollarını [A - Z, a - z] (2 ≤ n ≤ 100 000, 2 ≤ l ≤ 100 000) ehtiva edir. Kiçik və böyük hərflər fərqli simvollar hesab olunur. Testlərdə giriş/çıxış xərclərini azaltmaq üçün n × l ≤ 5 × 1 024 × 1 024.
Çıxış məlumatları
Uzunluğu l + n - 1 olan bir sətir çıxarın ki, girişdə verilən bütün sətirlər onun müxtəlif mövqelərdən başlayan alt sətirləri olsun. Belə bir sətirin mövcudluğu təmin edilir. Bir neçə cavab mümkündürsə, istənilən birini çıxarın.