Петата задача от нашия Конкурс е от една изключително интересна област на теоретичната информатика – търсенето на низ (образец) в друг низ (текст). Тази класическа задача има много разновидности, за решаването на който са известни алгоритми с различна сложност, зависещи не само от разновидността, но и от дължините на образеца и текста и броя на символите (буквите) в азбуката от която са съставени. Изключителният прогрес в областта в последните години се дължи до голяма степен на факта, че подобен род задачи се срещат често в една такава модерна научна дисциплина като генетиката.

В нашия случай става дума за неточно търсене, т.е. за такова търсене при което образецът може и да не се среща в текста във вида в който е зададен. При неточното търсене се допускат различни видове отклонения или несъответствия с текста. В задачата от петия кръг тези несъответствия са добавянето/изтриването на символ в образеца/текста или замяната на един символ с друг. Добавянето на символ в единия низ е еквивалентно на изтриване на символа от другия низ, който би съответствал на добавения символ. Ето защо е достатъчно да допускаме само една от двете операции добавяне и изтриване. Задачата е сходна с добре познатата задача, наричана най-дълга обща подредица на два низа. За решаването на тази разновидност съществува алгоритъм по схемата Динамично оптимиране, който е класика в жанра и може да се намери във всяка добра книга по алгоритми. Подобен подход може да реши и нашата задача.

Ето и накратко идеята за това решение. Да въведем следните означения: A за образеца, T за текста, La за дължината на образеца и Lt за дължината на текста. Нека за даден символен низ S с S[1..i] означим подниза на S започващ от 1-ва и завършващ на i-та позиция (i е по-малко или равно на дължината на S); и нека функцията f(i,j) ни дава с колко най-малко разлики A[1..i] се среща в T[1..j], като поднизът B от T[1..j], който съответства на А с f(i,j) разлики завършва в позиция j. Тогава f(La,j), 1<=j<=Lt, ни дава с колко най-малко разлики се среща образецът в текста, като срещането завършва в позиция j. Това j, за което стойността на f(La,j) е минимална, ще ни даде срещане на образеца в текста с възможно най-малко разлики. Да видим как можем да пресметнем f(i,j). Очевидно f(0,j)=0 за всяко възможно j (0<=j<=Lt), защото срещането на образеца в текста може да започва от произволна позиция на текста; а f(i,0)=i за всяко възможно i (0<=i<=La) защото P[1..i] може да съответства на празен низ само чрез изтриване на всичките му символи, които са i наброй. Лесно се вижда и рекурентната зависимост за f(i,j):

f(i,j)=min( f(i-1,j)+1, f(i,j-1)+1, f(i-1,j-1)+neq(P[i],T[j]) ) при 1<=i<=La и 1<=j<=Lt,

където за два символа x и y, neq(x,y)=1 при x¹y и neq(x,y)=0 при x=y. При наличието на няколко възможни отговора, условието на задачата изисква да се изведе това срещане, левият край на който е по-наляво. Това може лесно да се направи като “обърнем” (прочетем от дясно наляво, а не от ляво надясно) образеца и текста, и намерим стойностите на функцията f за обърнатите низове. Тогава, ще имаме по-ляв ляв край срещане на образеца в текста с минимално разлики, когато имаме по-десен десен край на срещане на обърнатия образец в обърнатия текст с минимално разлики, т.е. това j за което f(La,j) приема минималната възможна стойност, а j е колкото се може по-голямо. Вижда се обаче, че сложността на този алгоритъм е O(La*Lt).  Целта, разбира се е да се намери по-бърз алгоритъм.

            Естествено желание при нашата задача, в която се иска срещане с минимален брой разлики, е сложността на алгоритъма да зависи от броя на разликите K. Един такъв алгоритъм е със сложност O(K*Lt). Да разгледаме стандартната таблица на динамичното програмиране за решаване на задачи от подобен тип, която има La+1 реда и Lt+1 стълба. Нулевият ред и нулевият стълб се добавят по традиция и за удобство, както видяхме по-горе. Клетката с координати (i,j) ще съдържа стойността на f(i,j) според горната дефиниция.  Клетките с координати (i,i) образуват главния диагонал на таблицата. Да номерираме диагоналите над главния с числата 1,2,...,Lt, като диагоналът започващ в клетката (0,i) е номериран с i, а диагоналите под главния с числата -1,-2,..., -La, като диагоналът започващ в клетката (i,0) е номериран с -i.  Ще наричаме d-път в таблицата последователност от съседни клетки, започваща в реда с номер 0, вървяща само надолу, надясно или по диагонал надолу-надясно, която завършва в клетка, съдържаща числото d. Един d-път е най-далече стигащ за диагонала i, ако е d-път, завършващ с клетка на диагонала i, а стълбът j, в който завършва, е с максимален номер от всички стълбове, в които завършват d-пътища завършващи в диагонала i. Казано с други думи, d-път е най-далече стигащ за диагонала i, ако няма друг d-път стигащ до по-далечна (по-дясна) клетка на диагонала i. Най-общо казано, хибридният алгоритъм извършва К итерации, всяка със сложност O(Lt). На d-тата итерация алгоритъмът намира  най-далече стигащ d-път за всеки диагонал i, i= -La, -La+1,…,0,1,…,Lt. Всеки най-далече стигащ d-път, който завършва в реда La определя позиция в текста, в която завършва срещане на образеца с точно d разлики.

            Алгоритъмът започва със стойност на d=0; най-дългият 0-път завършващ в диагонала i отговаря на най-дългата обща представка на A[1..La] и T[i..Lt] (което се намира чрез най-дългото общо продължение(НОП) за позиция 1 и i на образеца и текста, съответно), защото 0-път не позволява разлики. Най-дълго общо продължение (longest common extension) за два символни низа S1 и S2, след предварителна обработка с линейна сложност спрямо дължините на низовете, за всеки две позиции i и j може да определи с константа сложност дължината на най-дългият подниз на S1 започващ от позиция i, който отговаря с 0 разлики на подниз на S2 започващ от позиция j. За повече информация относно НОП виж решението на зад.6 от миналогодишния конкурс; НОП(i,j) ще бъде етикета на върха, който е най-близък общ предшественик на лист i и лист j в обобщеното суфиксно дърво на S1 и S2. (В същност е достатъчно да се построи суфиксно дърво само на по-малкия от двата низа, но няма да се спираме на това.)

            За d>0  най-далече стигащият d-път за диагонала i може да се намери, като разгледаме следните три пътища, които завършват в диагонал i:

• Пътят R1, състоящ се от най-далече стигащият (d-1)-път за диагонала i+1, последван от движение в съседна клетка надолу (добавяне на един символ в текста) до диагонала i и завършващ с възможно най-далечно движение по диагонала i, което отговаря на идентични поднизове на образеца и текста; понеже пътя R1 започва с (d-1)-път и добавя само един символ, то R1 е d-път.
• Пътят R2, състоящ се от най-далече стигащият (d-1)-път за диагонала i-1, последван от движение в съседна клетка надясно (добавяне на един символ в образеца) до диагонала i и завършващ с възможно най-далечно движение по диагонала i, което отговаря на идентични поднизове на образеца и текста; R2 е d-път.
• Пътят R3, състоящ се от най-далече стигащият (d-1)-път за диагонала, последван от движение в съседна клетка надолу-надясно (отговарящо на замяна на символ) и завършващо с възможна най-далечно движение по диагонала i, което отговаря на идентични поднизове на образеца и текста; R3 е d-път.

Така за всички диагонали ще намерим най-далече стигащите d-пътища, като предаваме на d последователно стойностите 0, 1, 2… докато намерим път, който завършва в реда La и някоя колона j. Както казахме по-горе, това ни дава срещане на образеца в текста, което завършва в j-та позиция от текста. Така получаваме алгоритъм със сложност O(K*Lt), където K е минималния брой на разликите с които образеца се среща в текста.

            Също така, интересни са методите на R.Baeza-Yayes и C.Perleberg, на W.Chang и E.Lawler, и на G.Myers (http://www.cs.arizona.edu/http/html/people/gene/), които разбиват образеца (или текста) на последователни региони с определена големина; след което проверяват кои от тези региони могат да се съдържат в текста (или в образеца, ако текстът е бил разделен на части) при срещане образеца в текста с не повече от определен брой разлики К – тези региони се наричат “оцелели”; целта на това е да се елиминират колкото се може повече от регионите, след което за всеки оцелял регион да се провери дали има срещане на образеца в текста, съдържащо региона. Тези методи обикновено предполагат да се знае точната стойност на K и водят до алгоритми с очаквано линейна или подлинейна сложност. В нашата задача K не е известно, но можем да го намерим с идея подобна на идеята за двоично търсене – пробваме за К равно на 0, 1, 2, 4, 8 и т.н. докато получим стойност К’, за която намираме срещане на образеца в текста с най-много K’ разлики; след това намираме най-малката стойност К  чрез двоично търсене в интервала [K’/2,K’].

            Повечето участници с по-високи резултати за използвали идеята от статията на Gene Mayers A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming, която оставяме на любознателните читатели.