Genetik fırıldaqçılıq

Kompyuter alimlərinin həyatı çətindir. Sizin kimi parlaq gənc zəkaların çatışmazlığı səbəbindən, yaxşı proqramçılar əksər hallarda məşhur kino ulduzlarına bənzəyirlər. Elə bil ki, hər kəs sizin qan-tər içində qazandığınız pulları ələ keçirmək istəyir. Vəziyyət o qədər nəzarətdən çıxıb ki, demək olar ki, hər gün məhkəmə iddiaları ilə üzləşmək məcburiyyətindəsiniz. Hər bir iddia, sizin ehtimal olunan uşağınız üçün aliment tələb edən biri tərəfindən verilir. Xoşbəxtlikdən, siz genetik ardıcıllıqlar haqqında kifayət qədər məlumatlısınız. Siz bilirsiniz ki, insanın DNT ardıcıllığı yalnız 'a' ilə 'z' arasında olan simvollardan ibarət uzunluğu $n$ olan bir sıra ilə təmsil edilə bilər. Və siz bilirsiniz ki, ehtimal olunan uşağın DNT zəncirlərinin sizin öz zəncirlərinizlə oxşarlığını yoxlamaq sizin günahsızlığınızı sübut edə bilər.

Yeganə problem ondadır ki, bu yalnız sizinlə baş vermir. Bütün laboratoriyalar məşğul olduğu üçün testlər ən azı bir il çəkəcək. Lakin bütün ümidlər itirilməyib. Siz laboratoriyalardan birində DNT məlumatlarını əldə etməyə müvəffəq oldunuz ki, iki DNT zənciri arasında genetik qohumluq ehtimalını necə hesablamaq olar. Əgər siz DNT laboratoriyalarına iki DNT zəncirini genetik qohumluq üçün çox tez yoxlamaqda kömək edə bilsəydiniz, öz məhkəmə iddialarınız üçün lazım olan sübutları əldə edə bilərdiniz.

Genetik qohumluq testi, yaxud GQT, DNT zəncirlərində bəzi çətin hesablamalar tələb edir. Əvvəlcə iki DNT zəncirindəki bütün oxşar sahələr nəzərdən keçirilir. DNT zəncirinin sahəsi dedikdə, DNT zəncirində ardıcıl interval nəzərdə tutulur. a[i .. i + l]~(0 \le i < n - l) və b[j..j+l]~(0 \le j < n - l) DNT zəncirlərinin $a,b$ sahələri bir-birinə oxşardır, əgər |a[i+k] - b[j+k]| \le 1 üçün 0 \le k \le l. İki DNT ardıcıllığı arasında GQT müsbətdir, əgər iki DNT ardıcıllığı ən azı ardıcıllıqların yarısı uzunluğunda oxşar sahəyə malikdirsə.