Cautarea de siruri directa

Cautarea de siruri directa

O maniera frecvent intalnita de cautare este asa numita cautare de siruri directa ('string search').

Cea mai simpla metoda de cautare este asa numita cautare de siruri directa.

Rezultatul unei astfel de cautari este un indice i care precizeaza aparitia unei coincidente intre model si sir.

Analiza cautarii de siruri directe.

Algoritmul lucreaza destul de eficient daca se presupune ca nepotrivirea in procesul de cautare apare cel mult dupa cateva comparatii in cadrul buclei interioare.

Astfel pentru un set de 128 de caractere se poate presupune ca nepotrivirea apare dupa inspectarea a 1 sau 2 caractere.

Cu toate acestea in cazul cel mai nefavorabil, degradarea performantei este ingrijoratoare.

Astfel daca spre exemplu sirul s este format din n-1 caractere 'A' urmate de un singur 'B',

Iar modelul consta din m-1 caractere 'A' urmate de un 'B',

In acest caz este necesar un numar de comparatii de ordinul n  m pentru a gasi coincidenta la sfarsitul sirului.

Din fericire exista metode care imbunatatesc radical comportarea algoritmului in aceasta situatie.

Tehnicile de cautare care sunt prezentate in continuare materializeaza acest deziderat.