Şahzadə ya da saxtakar
U qədim zamanlarda, keçmiş əsrlərdə və yüzilliklərdə Farsda böyük şah Daranın hökmranlığı vardı. O zamanlar Fars dövləti çiçəklənirdi və hər şey bolluq içində idi. Bir gün şahın oğlu dünyaya gəldi və o gün yerdə Dardan daha xoşbəxt bir insan yox idi. Bu hadisənin şərəfinə böyük bir bayram təşkil etdi. Lakin varisin doğulması münasibətilə keçirilən bütün mərasimlər zamanı Daranın düşmənləri tərəfindən tutulmuş qatilər yataq otağına girib uşağı oğurladılar. Dara dəhşətli dərəcədə qəzəbləndi və mühafizəçilərin edamını əmr etdi. Bundan əlavə, şah axtarış elan etdi və şahzadəni saraya qaytaran şəxsə böyük mükafat vəd etdi...
...Günlər, həftələr, aylar və illər keçdi, lakin şah oğlundan heç bir xəbər almadı. Və beləliklə, axtarışların on səkkizinci ili gəldikdə, saraya gözlərində parıltı olan uzun boylu bir gənc daxil oldu və özünü itmiş şahzadə kimi təqdim etdi. Gənc inanılmaz hekayələr danışırdı. Onu adi bir balıqçının ailəsinə necə atdıqlarını, balıqçıya şahzadə haqqında heç kimə danışmamağı ölüm təhdidi ilə necə qadağan etdiklərini, bütün bu illər ərzində necə yaşadığını və qoca balıqçının ölüm anında ona mənşəyi haqqında dəhşətli bir sirr açdığını danışırdı.
Dara artıq gəncə inanmağa və onu qucaqlamağa hazır idi, lakin vəzir şaha tələsməməyi və əvvəlcə yoxlama aparmağı tövsiyə etdi. Məlumdur ki, insan orqanizminin hər hüceyrəsi nukleotidlər zəncirindən ibarət olan və A, G, T, C simvolları ilə kodlanan DNT-ni ehtiva edir və bu zəncirlər yaxın qohumlarda oxşar olmalıdır. Vəzir gəncin DNT-sindən bir fraqment götürməyi və müəyyən bir mövqedən başlayaraq şahın DNT-si ilə müqayisə etməyi təklif etdi. Aydındır ki, ən yaxşı variant fraqmentin seçilmiş mövqedən dəqiq uyğun gəldiyi zaman olacaq. Ancaq ümumiyyətlə, oxşarlıq dərəcəsi uyğun elementlərin müqayisəsi zamanı uyğunluqların sayı hesab ediləcək. Vəzir və şah sizdən oxşarlıq dərəcəsinin maksimum olması üçün müqayisəyə başlayacağınız mövqeni müəyyən etməyinizi xahiş edirlər.
Giriş verilənləri
Birinci sətirdə şahın DNT-si – A, G, T, C simvollarının ardıcıllığı verilir. İkinci sətirdə eyni şəkildə gəncin DNT fraqmenti verilir. Sətirlərin uzunluğu 200000-dən çox deyil və ikinci sətir birincidən uzun deyil.
Çıxış verilənləri
Oxşarlığın mümkün qədər yüksək olması üçün müqayisəyə başlayacağınız mövqenin nömrəsini göstərin. Əgər belə mövqelər bir neçə olarsa, birincisini göstərin. Mövqelər 1-dən başlayaraq nömrələnir.