Algoritmul Boyer-Moore

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 iulie 2018; verificările necesită 28 de modificări .

Algoritmul Boyer-Moore
Numit după	Robert S. Boyer [d] și J Strother Moore [d]
Autor	Robert S. Boyer [d] și J Strother Moore [d]
scop	Căutare eficientă a unui subșir într-un șir
Structură de date	Siruri de caractere
cel mai rău moment	$\Theta (n+m)$
Costul memoriei	$\Theta (m+\|\Sigma \|)$ sau $\Theta (m)$
Fișiere media la Wikimedia Commons

Algoritmul de căutare a șirurilor Boyer-Moore este un algoritm de uz general conceput pentru a căuta un subșir într-un șir . Proiectat de Robert Boyerși Jay Mooreîn 1977 [1] . Avantajul acestui algoritm este că, cu prețul unui anumit număr de calcule preliminare asupra șablonului (dar nu și asupra șirului în care se face căutarea), șablonul nu este comparat cu textul sursă în toate pozițiile - unele dintre verificări sunt sărite deoarece evident că nu dă un rezultat.

O estimare generală a complexității de calcul a versiunii moderne a algoritmului Boyer-Moore este , dacă nu este utilizat tabelul de caractere stop (vezi mai jos), și dacă este folosit tabelul de caractere stop, unde este lungimea șirului căutat , este lungimea modelului de căutare, este alfabetul , pe care se face comparația [2] . $O(n+m)$ $O(n+m+|\Sigma |)$ $n$ $m$ $\Sigma$

Descrierea algoritmului

Algoritmul se bazează pe trei idei.

1. Scanați de la stânga la dreapta, comparați de la dreapta la stânga. Începutul textului (linia) și modelul sunt combinate, verificarea începe de la ultimul caracter al modelului. Dacă caracterele se potrivesc, penultimul caracter al modelului este comparat și așa mai departe. Dacă toate caracterele din model se potrivesc cu caracterele suprapuse ale șirului, atunci subșirul a fost găsit și următoarea apariție a subșirului este căutată.

Dacă un caracter al modelului nu se potrivește cu caracterul corespunzător al șirului, modelul este deplasat cu câteva caractere la dreapta și testul începe din nou de la ultimul caracter.

Aceste „puține” menționate în paragraful anterior sunt calculate după două euristici.

2. Euristică simbol de oprire. ( Notă: euristica simbolului stop este prezentă în majoritatea descrierilor algoritmului Boyer-Moore, inclusiv în articolul original al lui Boyer și Moore [1] , dar nu este necesară pentru a realiza estimarea timpului de rulare [2] ; în plus, această euristică necesită memorie suplimentară de lucru și timp suplimentar în timpul pregătirii șablonului.) $O(n+m)$ $O(|\Sigma |)$ $O(|\Sigma |)$

Să presupunem că căutăm cuvântul „clopot”. Prima literă nu se potrivea - „k” (să numim această literă un simbol stop ). Apoi puteți muta șablonul la dreapta la ultima sa literă „k”.

Șir: * * * * * * la * * * * * * Şablon: k o l o k o l Următorul pas: k o l o k o l

Dacă nu există niciun caracter de oprire în model, modelul este deplasat dincolo de acel caracter de oprire.

Șir: * * * * * a l * * * * * * * * Şablon: k o l o k o l Următorul pas: k o l o k o l

În acest caz, caracterul stop este „a”, iar modelul este deplasat astfel încât să fie chiar în spatele acelei litere. În algoritmul Boyer-Moore, euristica caracterului de oprire nu se uită deloc la sufixul potrivit (vezi mai jos), astfel încât prima literă a modelului ("k") va fi sub "l" și un manechin cunoscut. se va face verificarea.

Dacă simbolul stop „k” se află în spatele altei litere „k”, euristica simbolului stop nu funcționează.

Șir: * * * * la c o l * * * * * Şablon: k o l o k o l Următorul pas: k o l o k o l

În astfel de situații, a treia idee a algoritmului Boyer-Moore vine în ajutor - sufixul euristic potrivit.

3. Euristică a sufixului potrivit. În mod informal, dacă sufixul S este potrivit în timp ce se citește modelul de la dreapta la stânga, dar caracterul b care precede S în model (adică modelul este PbS) nu se potrivește, atunci sufixul euristic potrivit schimbă modelul cu cel mai mic număr de locuri la dreapta, astfel încât șirul S să se potrivească cu modelul, iar caracterul care precedă potrivirea dată S în model ar fi diferit de b (dacă există un astfel de caracter). În mod formal, pentru acest șablon, se ia în considerare o matrice întreagă sufshift[0..m], în care sufshift[i] este egal cu numărul minim astfel încât (dacă și ) și pentru oricare pentru care și este valabil (a se vedea exemplele de mai jos pentru explicație ). Apoi, dacă în timp ce citiți modelul de la dreapta la stânga , caracterele s-au potrivit , dar caracterul nu s-a potrivit, atunci modelul este mutat sufshift[mk] caractere la dreapta. De exemplu: $s[0..m{-}1]$ $j>0$ $s[i{-}j]\neq s[i{-}1]$ $i>0$ $ij\geq 0$ $s[i{-}j{+}k]=s[i{-}1{+}k]$ $k>0$ $0\leq i-j+k<m$ $0\leq i-1+k<m$ $s$ $k{-}1$ $s[m{-}1],s[m{-}2],\ldots ,s[m{-}k{+}1]$ $s[m{-}k]$

Linie: * * * * * * p la a * * * * * Şablon: s ka l k a l k a Următorul pas: c a l c a l c a

În acest caz, sufixul „ka” s-a potrivit, iar modelul este mutat la dreapta la cel mai apropiat „ka” care nu are un „l” în fața lui.

Șir: * * t o c o l * * * * * Şablon: k o l o k o l Următorul pas: k o l o k o l

În acest caz, sufixul „aproape” s-a potrivit, iar șablonul este deplasat la dreapta la cel mai apropiat „aproape” care nu are un „l” în fața lui. Dacă subșirul „despre” nu mai este în model, dar începe cu „număr”, trece la „număr”, etc.

Avertisment : O nepotrivire a literei înainte de apariția cea mai apropiată a unui sufix de potrivire este o condiție prealabilă. Dacă ne limităm la trecerea la cea mai apropiată apariție a unui sufix potrivit, atunci algoritmul poate funcționa inacceptabil de lent. De exemplu, atunci când se caută un model de lungime într-un șir care conține caracterele „a” urmate de un șir de lungime , un algoritm care utilizează deplasări fără a ține cont de nepotrivirile de caractere efectuează operații chiar și atunci când folosește euristica caracterului stop. Pe de altă parte, s-a dovedit [2] că timpul de rulare al algoritmului BM, ținând cont de nepotrivirea caracterelor (adică folosind matricea sufshift definită mai sus), este egal chiar și fără a utiliza euristica caracterului stop ( dată în cartea lui M. Kroshmore şi W. Ritter [2] dovada acestui fapt este o modificare a demonstraţiei lui Cole din 1994 [3] , care a luat în considerare doar cazul modelelor neperiodice). $cabababa\ldots ba$ $2n$ $aaa\ldots aababab\ldots ba$ $2n$ $baba\ldotsba$ $2n$ $O(n^{2})$ $O(n+m)$

Ambele euristice necesită calcule prealabile - în funcție de modelul de căutare, două tabele sunt completate. Tabelul simbolurilor de oprire corespunde ca dimensiune alfabetului - (de exemplu, dacă alfabetul este format din 256 de caractere, atunci lungimea sa este de 256); tabel de sufixe - la modelul dorit, adică . $O(|\Sigma |)$ $O(m)$

Să descriem ambele tabele mai detaliat.

Tabelul cu simboluri de oprire

Tabelul cu caractere de oprire listează ultima poziție din model ( excluzând ultima literă ) a fiecărui caracter din alfabet. Pentru toate caracterele care nu sunt incluse în , scriem 0 dacă numerotarea caracterelor începe de la 1 (sau −1 dacă numerotarea începe de la 0). De exemplu, dacă , tabelul de caractere stop StopTable va arăta astfel (tabelul este dat pentru cazul unui șir numerotat de la zero; atunci când numerotați caracterele de la unu, trebuie să adăugați unul la toate numerele): $s$ $s$ $s=abcdadcd$

Simbol abcd [toate celelalte] Ultima poziție 4 1 6 5 -1

Rețineți că pentru caracterul stop „d”, ultima poziție va fi 5, nu 7 - ultima literă nu este luată în considerare. Acesta este un bug cunoscut care duce la suboptimalitate. Pentru algoritmul BM, nu este fatal (euristica sufixului salvează situația), dar este fatal pentru o versiune simplificată a algoritmului BM - algoritmul Horspool .

Dacă, când se compară modelul cu șirul de la dreapta la stânga , nepotrivirea a avut loc la poziția , iar caracterul de oprire este , atunci modelul trebuie deplasat cu caractere. $s[0..m{-}1]$ $text[i..i{+}m{-}1]$ $j$ $c=text[j]$ $i'=j-StopTable[c]$

Tabel cu sufixe

Pentru fiecare sufix posibil al modelului dat , specificăm cea mai mică cantitate cu care modelul trebuie să fie mutat la dreapta, astfel încât să se potrivească din nou și, în același timp, caracterul care precede această apariție să nu se potrivească cu caracterul care precede sufixul . Dacă o astfel de schimbare nu este posibilă, puneți (în ambele sisteme de numerotare). De exemplu, pentru va fi: $t$ $s$ $t$ $t$ $t$ $|s|=m$ $s=aaccbccbcc$

Sufix [blank] c cc bcc ... aaccbccbcc Offset 2 1 6 10 ... 10 Ilustrare A fost ? ?c ?cc ?bcc ... aaccbccbcc a devenit aaccbccbcc aaccbccbcc aaccbccbcc aaccbccbcc ... aaccbccbcc

Pentru „clopot”: $s=$

Sufix [blank] l ol kol ... okol bell Shift 1 7 7 4 ... 4 4 Ilustrare A fost ? ?l ?ol ?kol ... ?ring the bell a devenit clopot clopot clopot clopot ... clopot clopot

Există un algoritm pentru calcularea tabelului sufix sufshift[0..m] cu timpul de rulare . [2] Acest algoritm se bazează pe aceleași idei ca și algoritmii de calcul al funcției de prefix și al funcției șir Z [4] [5] . Implementarea acestui algoritm în C++ este următoarea: $O(m)$

std :: vector < int > suffshift ( m + 1 , m ); std :: vector < int > z ( m , 0 ); pentru ( int j = 1 , maxZidx = 0 , maxZ = 0 ; j < m ; ++ j ) { dacă ( j <= maxZ ) z [ j ] = std :: min ( maxZ - j + 1 , z [ j - maxZidx ]); în timp ce ( j + z [ j ] < m && s [ m - 1 - z [ j ]] == s [ m - 1 - ( j + z [ j ])]) z [ j ] ++ ; dacă ( j + z [ j ] - 1 > maxZ ) { maxZidx = j ; maxZ = j + z [ j ] - 1 ; } } pentru ( int j = m - 1 ; j > 0 ; j -- ) suffshift [ m - z [ j ]] = j ; //bucla #1 pentru ( int j = 1 , r = 0 ; j <= m - 1 ; j ++ ) //bucla #2 dacă ( j + z [ j ] == m ) pentru (; r <= j ; r ++ ) if ( sufshift [ r ] == m ) sufshift [ r ] = j ;

În prima buclă din cod, este reprodus codul pentru calcularea așa-numitei funcție Z , dar pentru șirul inversat . [5] Și anume, pentru orice astfel încât , elementul conține lungimea celui mai lung sufix al șirului , care este și sufixul întregului șir . Folosind matricea , se calculează apoi matricea dorită suffshift[0..m] (vezi descrierea de mai jos). La fiecare iterație a ultimei bucle , aceasta scade cu 1, iar la fiecare iterație a buclei imbricate în ea, scade cu 1. Prin urmare, deoarece , , și algoritmul pentru calcularea funcției Z funcționează pentru (vezi, de exemplu , articolul corespunzător , precum și articolul [5] ) , timpul total de rulare al acestui algoritm este de . $z[1..m{-}1]$ $s[0..m-1]$ $j$ $0\leq j<m-1$ $z[m-1-j]$ $s[0..j]$ $s$ $z$ $j$ $k$ $j\geq 0$ $k\geq 0$ $O(m)$ $O(m)$

Pentru a demonstra corectitudinea codului prezentat, este convenabil să ne imaginăm că șirul este parsat , ceea ce este egal cu șirul inversat . După definiția sufshift, avem uffshift[ ] , unde este cel mai mic număr pozitiv astfel încât fie 1) șirul este un prefix al șirului , fie 2) șirul este egal cu și caracterele și sunt diferite. În cazul 2), prin definiție , este în mod necesar satisfăcut . Astfel, parcurgând de la la 1, bucla #1 găsește toate valorile suffshift obținute prin regula 2). Pentru a calcula valorile sufshift obținute prin regula 1), observăm că, în primul rând, dacă este un prefix , atunci este în mod necesar satisfăcut , iar în al doilea rând, dacă sufshift[ ] = pentru unii , atunci este în mod necesar . Pe baza acestor două observații, bucla #2 calculează valorile rămase neinițializate sufshift (adică, astfel încât sufshift[k] = m). $s'[0..m{-}1]$ $s$ $mk$ ${\displaystyle=j}$ $j$ $s'[j..m{-}1]$ $s'[0..k{-}1]$ $s'[j..j{+}k{-}1]$ $s'[0..k{-}1]$ $s'[j{+}k]$ $s'[k]$ $z$ $z[j]=k$ $j$ $m-1$ $s'[j..m{-}1]$ $s'[0..k{-}1]$ $j+z[j]=m$ $r$ $j$ $r$ $r\leq j$

Implementarea algoritmului

Fie numărată șirul de schimburi sufshift[0..m] pentru șablonul dat . Apoi, implementarea C++ a algoritmului Boyer-Moore pentru găsirea primei apariții într-un text în timp fără a utiliza euristica caracterului stop este următoarea [2] : $s[0..m{-}1]$ $s$ $text[0..n{-}1]$ $O(n+m)$

pentru ( int i = 0 , j = 0 ; i <= n - m && j >= 0 ; i += suffshift [ j + 1 ]) { pentru ( j = m - 1 ; j >= 0 && s [ j ] == text [ i + j ]; j -- ); if ( j < 0 ) report_occurrence ( i ); }

Un astfel de algoritm nu este potrivit pentru găsirea în timp a tuturor aparițiilor unui model într-un text . Dacă eliminăm condiția „j >= 0” din bucla exterioară, atunci algoritmul va găsi toate aparițiile, dar, în cel mai rău caz, poate efectua operații, care pot fi observate cu ușurință luând în considerare un șir format doar din literele " A". Pentru a căuta toate aparițiile, se folosește următoarea modificare, care funcționează în timp datorită așa-numitei reguli Galil [6] : $O(m+n)$ $O(mn)$ $O(n+m)$

int j , legat = 0 ; //intotdeauna fie legat = 0, fie legat = m - suffshift[0] pentru ( int i = 0 ; i <= n - m ; i += suffshift [ j + 1 ]) { pentru ( j = m - 1 ; j >= legat && s [ j ] == text [ i + j ]; j -- ); dacă ( j < legat ) { raport_ocurență ( i ); legat = m - suffshift [ 0 ]; j = -1 _ //setăm j ca și cum am citi întregul model s, nu doar până la limita } else { legat = 0 ; } }

Regula lui Galil se bazează pe următoarea observație simplă. Dacă se găsește o apariție la poziția , atunci următoarea căutare va încerca să găsească o apariție a modelului la poziția sufshift[0] și, prin definiția sufshift, se știe deja că caracterele se potrivesc cu cele ale sufshift[0] . Deci, atunci când se efectuează o căutare de la dreapta la stânga pentru a determina dacă există o apariție a modelului la poziția , nu are rost să verifici caracterele sufshift[0] . Pentru asta este variabila „legată”. S-a dovedit că o astfel de euristică ajută la obținerea timpului necesar pentru a căuta toate aparițiile modelului din șir [6] . $s$ $i$ $i'=i+$ $s[i'],s[i'{+}1],\ldots ,s[i{+}m{-}1]$ $s[0],s[1],\ldots,s[m{-)$ ${-}1]$ $eu$ $s[0],s[1],\ldots,s[m{-)$ ${-}1]$ $O(n+m)$

Pentru a activa euristica simbolului stop, este suficient i += suffshift[j+1]să înlocuiți linia „ ” cu următoarea expresie la sfârșitul buclei principale:

dacă ( j < legat ) i += sufshift [ j + 1 ]; else i += max ( suffshift [ j + 1 ], j - StopTable [ text [ i + j ]]);

Un exemplu despre cum funcționează algoritmul

Modelul dorit este " abbad". Tabelul cu simboluri de oprire va arăta astfel (în acest exemplu, va fi mai convenabil să utilizați numerotarea de la unul)

Simbol abd [altele] Poziția 4 3 5 0

Tabelul de sufixe pentru toate sufixele posibile (cu excepția celor goale) oferă o schimbare maximă de 5.

abeccaabadbabbad abbad

Impunem un eșantion pe linie. Nu există potrivire de sufixe - tabelul de sufixe oferă o schimbare cu o poziție. Pentru caracterul nepotrivit al șirului sursă " с" (a 5-a poziție), în tabelul cu caractere de oprire este scris 0. Mutați modelul la dreapta după 5-0=5poziții.

abeccaabadbabbad abbad

Simbolurile 3-5 s-au potrivit, dar al doilea nu. Euristica pentru „ а” nu funcționează ( 2-4=-2). Dar, deoarece unele dintre personaje s-au potrivit, euristica sufixului potrivit intră în joc, schimbând modelul cu cinci poziții deodată!

abeccaabadbabbad abbad

Din nou, nu există nici un sufix potrivit. În conformitate cu tabelul cu caractere de oprire, deplasăm eșantionul cu o poziție și obținem apariția dorită a eșantionului:

abeccaabadbabbad abbad

Dovada corectitudinii

Pentru a demonstra corectitudinea algoritmului, este suficient să arătăm că, dacă una sau alta euristică sugerează o deplasare cu mai mult de o poziție spre dreapta, modelul nu va fi găsit în pozițiile lipsă.

Deci, să se potrivească sufixul S , șirul șablonului este egal cu PbS , caracterul stop este a (în continuare, literele mici sunt simboluri, literele mari sunt șiruri).

Șir: * * * * * * * a [-- S --] * * * * Model: [--- P ---] b [-- S --]

Euristică simbol stop. Funcționează când nu există niciun caracter în șirul V. Dacă P=WaV și nu există niciun caracter în șirul V , atunci euristica caracterului stop sugerează o schimbare cu | V |+1 poziție.

Șir: * * * * * * * * * * * * a [-- S --] * * * * * * * * Model: [- W -] a [--- V ---] b [-- S --] Omite: [- W -] a [--- V ---] b [-- S --] Pas nou: [- W -] a [--- V ---] b [-- S --]

Într-adevăr, dacă șirul V nu conține litera a , nu există nimic de încercat pentru | v | pozitii.

Dacă nu există un caracter în model , atunci euristica caracterului de oprire sugerează o schimbare cu | P |+1 poziție - și, de asemenea, nu are sens să încerci | lipsă P |.

Șir: * * * * * * * * a [-- S --] * * * * * * * * Model: [--- P ---] b [-- S --] Omite: [--- P ---] b [-- S --] Pas nou: [--- P ---] b [-- S --]

Sufix euristic potrivit. Expresia informală în sine - „cea mai mică cantitate pe care modelul trebuie să fie deplasată la dreapta pentru a se potrivi din nou cu S, dar caracterul înainte de potrivirea dată cu S (dacă un astfel de caracter există) ar fi diferit de b” - spune că mai mic turele sunt inutile.

Opțiuni

Algoritmul Boyer-Moore-Horspool

Algoritmul Boyer-Moore-Horspool (ABMH) funcționează mai bine decât algoritmul Boyer-Moore (ABM) pe texte aleatorii - estimarea medie este mai bună pentru acesta.

ABMX folosește doar euristica simbolului stop; caracterul de oprire este considerat caracterul șirului de intrare care se potrivește cu ultimul caracter al modelului, indiferent de locul în care a avut loc nepotrivirea .

Deoarece eșantioanele de căutare reale au rareori o distribuție uniformă , ABMS poate oferi atât un câștig, cât și o pierdere în comparație cu ABM.

Algoritmul Zhu-Takaoka

Pe alfabetele scurte (de exemplu, când se compară segmente de ADN , alfabetul este format din doar patru caractere: A , T , G , C ) euristica caracterului stop eșuează deja pe sufixele scurte. Cel mai simplu mod de a îmbunătăți performanța ABM în astfel de condiții este construirea unui tabel pentru o pereche de caractere în loc de un caracter stop: cel care nu s-a potrivit și cel care vine înaintea lui [7] . Un astfel de algoritm a fost numit algoritmul Zhu-Takaoka.

Preprocesarea necesită timp. $O(m+|\Sigma |^{2})$

Algoritmul Turbo-Boyer-Moore

Algoritmul turbo-Boyer-Moore a fost dezvoltat de un grup de oameni de știință condus de M. Kroshmore , oferă o abordare diferită a alfabetelor scurte și, în același timp, rezolvă a doua problemă - complexitatea pătratică în cel mai rău caz.

Pe lângă euristica caracterului de oprire și euristica sufixului potrivit, se aplică o a treia euristica, euristica turboshift [8] .

Lăsați sufixul UV să se potrivească prima dată (și sufixul euristic a funcționat, oferind o suprapunere completă a acestui sufix), a doua oară - un V mai scurt (eventual V = ∅).

! ! șir de intrare: * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * * 1. UV potrivite: * [-U-] [V] * * * * [-U-] [V] 2. Apoi V s-a potrivit: * [-U-] [V] * * * * * * [-U-] [V] Deplasare euristică a sufixului: * [-U-] [V] * * * * * * [-U-] [V] Turboschift: * [-U-] [V] * * * * * * [-U-] [V]

Figura arată că deplasarea minimă posibilă este | U |. În caz contrar, cele două caractere indicate prin semne de exclamare sunt diferite în șirul de intrare, dar aceleași în model. Aceasta este euristica turboshift.

Algoritmul își face treaba pentru comparații cu prima potrivire în cel mai rău caz. $2n$

Comparație cu alți algoritmi

Avantaje

Algoritmul Boyer-Moore este foarte rapid pe date „bune”.[ clarifica ] , iar probabilitatea apariției datelor „proaste” este extrem de mică. Prin urmare, este optim în majoritatea cazurilor când nu este posibilă preprocesarea textului în care se efectuează căutarea [9] . Cu excepția cazului în texte scurte, câștigul nu va justifica calcule preliminare.

Dezavantaje

Algoritmii familiei Boyer-Moore nu se extind la o căutare aproximativă, căutarea oricărui șir din mai multe.

Comparația nu este o „ cutie neagră ” (doar dacă se folosește euristica cu caracter stop), așa că atunci când implementați cea mai rapidă căutare, fie trebuie să vă bazați pe optimizator pentru a funcționa cu succes , fie să optimizați manual căutarea în limbaj de asamblare.

Dacă textul se modifică rar și căutarea este efectuată frecvent (de exemplu, de un motor de căutare ), puteți indexa textul. Algoritmul de căutare index este mai rapid[ clarifica ] algoritmul Boyer-Moore.

Pe alfabetele mari (cum ar fi Unicode ), tabelul cu caractere de oprire poate ocupa multă memorie. În astfel de cazuri, fie tabelele hash sunt eliminate cu , fie alfabetul este împărțit, luând în considerare, de exemplu, un caracter de 4 octeți ca o pereche de caractere de doi octeți, fie (care este cel mai simplu) folosesc o variantă a lui Boyer. -Algoritm Moore fără euristica caracterelor stop.

Există o serie de modificări ale algoritmului Boyer-Moore care vizează o accelerare și mai mare - de exemplu, algoritmul turbo, algoritmul invers Colussi [10] și altele.

Vezi și

Note

↑ 12 Boyer , Moore, 1977 .
↑ 1 2 3 4 5 6 Crochemore, Rytter, 2002 .
↑ Cole, 1994 .
↑ Gasfield, 2003 .
↑ 1 2 3 MAXimal :: algo :: Funcția Z șir și calculul acesteia . Preluat la 14 martie 2017. Arhivat din original la 26 aprilie 2017. (nedefinit)
↑ 12 Galil , 1979 .
↑ Algoritmul Zhu-Takaoka Arhivat 16 decembrie 2008 la Wayback Machine
↑ Algoritmul Turbo-BM Arhivat 16 decembrie 2008 la Wayback Machine
↑ Algoritmi de potrivire exactă a șirurilor - Introducere Arhivată 16 decembrie 2008 la Wayback Machine
↑ Algoritmul Reverse Colussi Arhivat 9 martie 2016 la Wayback Machine

Literatură

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algorithms: construction and analysis = Introduction to Algorithms / ed. S. N. Triguba ; pe. din engleza. I. V. Krasikov , N. A. Orehov ,N. Romanov - Ed. a II-a. - M. : Williams, 2005. - 801 p. — ISBN 5-8459-0857-4 .
Crochemore M. , Rytter W. Jewels of Stringology. Singapore: World Publishing Scientific Co. Pte. Ltd., 2002. - 310 p. — ISBN 981-02-4782-6 .
Boyer RS , Moore JS Un algoritm rapid de căutare a șirurilor // Comunicațiile ACM . - 1977. - T. 20 , nr 10 . - S. 762-772 . doi :/ 359842.359859 .
Cole R. Limite strânse ale complexității algoritmului de potrivire a șirurilor Boyer-Moore // SIAM Journal on Computing . - 1994. - T. 23 , nr 5 . - S. 1075-1091 . - doi : 10.1137/S0097539791195543 .
Galil Z. Cu privire la îmbunătățirea timpului de rulare în cel mai rău caz al algoritmului de potrivire a șirurilor Boyer-Moore // Comunicații ale ACM . - 1979. - T. 22 , nr 9 . - S. 505-508 . - doi : 10.1145/359146.359148 .
Gasfield D. Strings, trees and sequences in algorithms: computer science and computational biology = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology / transl. din engleza. I. V. Romanovski . - Sankt Petersburg. : Dialectul Nevski, 2003. - 654 p. — ISBN 5-7940-0103-8 .

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun