GATTACA
İnstitut Bioinformatika və Tibb (İBM) ölkənizdə bəzi orqanizmlərin, o cümlədən insanın DNT-sini öyrənməklə məşğuldur. Orqanizmin DNT-sini təhlil etməzdən əvvəl tədqiqatçılar orqanizmin hüceyrələrindən DNT əldə etməli və onu "sekvenləşdirmə" adlanan proses vasitəsilə deşifrə etməlidirlər.
DNT ardıcıllığını deşifrə etmək üçün istifadə olunan metod "parçalanmış sekvenləşdirmə" adlanır. Bu metod, eyni DNT-nin bir çox təsadüfi nüsxəsini kiçik fraqmentlərə bölərək uzun DNT zəncirlərini deşifrə etmək üçün tətbiq olunur. Metod xüsusi bir maşın vasitəsilə DNT-nin simvollarını (A, C, G və T) ardıcıl olaraq oxuyur, sonra isə xüsusi bir alqoritm istifadə edərək bütün ardıcıllığı qurmaq üçün onları bir araya gətirir.
Adətən, DNT zənciri ardıcıllıqda iki və ya daha çox dəfə təkrarlanan bir çox seqmentə malikdir (bu seqmentlər "təkrarlar" adlanır). Təkrarlar parçalanmış sekvenləşdirmə metodu ilə tam müəyyən edilmir, çünki montaj prosesi iki yeni eyni alt zəncir fraqmentini iki ayrı təkrardan fərqləndirə bilmir.
İnstitutun alimləri daha bahalı bir sekvenləşdirmə metodu ilə bir ailədən olan bir çox bakteriyanın DNT-sini uğurla deşifrə etdilər ki, bu da təkrarlar probleminin qarşısını aldı. Bioloqlar bunu boş yerə xərclənən vəsait hesab edirlər, çünki onların fikrincə, öyrənilən bakteriyaların DNT-sində böyük təkrarlanan fraqmentlər yoxdur.
Bioloqlar sizdən verilmiş DNT ardıcıllığında ən azı iki dəfə təkrarlanan ən böyük alt zənciri müəyyən edən bir proqram yazmağınızı istəyirlər.
Giriş verilənləri
Giriş faylının ilk sətirində testlərin sayını göstərən tam ədəd T (1 ≤ T ≤ 100) verilir. Hər bir test bir DNT ardıcıllığı olan S mətnindən ibarətdir, uzunluğu n (1 ≤ n ≤ 1000).
Hər bir S ardıcıllığı yalnız A, C, G və T hərflərini ehtiva edir.
Çıxış verilənləri
Hər bir giriş ardıcıllığı üçün əvvəlcə S sətirində ən azı iki dəfə təkrarlanan ən böyük alt zənciri, sonra isə boşluqla onun S-dəki təkrarlanma sayını bir sətirdə çıxarın.
Əgər maksimal uzunluqda iki və ya daha çox təkrarlanan alt zəncir varsa, leksikoqrafik olaraq ən kiçiyini çıxarın.
Əgər S-də təkrarlar yoxdursa, "No repetitions found!" mesajını çıxarın.