Kapitola 5.

Vyhľadávanie v reťazcoch

 
 
Ďalším typom vyhľadávacích úloh je vyhľadávanie zadaného vzoru v reťazci znakov. Aj vzor je vlastne reťazec, budeme ho však ďalej nazývať vzor a tak ho odlišovať od reťazca, v ktorom tento vzor vyhľadávame. Pri práci s veľkým množstvom textu potrebujeme niekedy nájsť nami zadané slovo. Algoritmus vyhľadávania musí prejsť celý text (reťazec) a porovnávať postupnosť znakov v texte s nami zadanou postupnosťou znakov (vzor). Zoznámime sa s tromi takýmito algoritmami.
 
Výstupom týchto algoritmov je index prvého znaku v reťazci, od ktorého sa postupnosť znakov v reťazci zhoduje s postupnosťou znakov vo vzore. Dĺžku vzoru, teda počet znakov, ktoré vzor obsahuje budeme označovať m a počet znakov reťazca budeme ďalej v tejto kapitole označovať n. Počet prvkov abecedy, teda koľko rôznych znakov existuje v použitej abecede, budeme označovať písmenom c. Vzor a reťazec môžu pozostávať iba zo znakov, ktoré obsahuje abeceda.
 
Teraz si uvedieme tri algoritmy, na ktorých si ukážeme aké techniky sa pri vyhľadávaní používajú. Viac vyhľadávacích algoritmov používaných pre reťazce môžeme nájsť v [7], [8], [12] a [13].

Zoznam stránok venujúcich sa vyhľadávaniu vzoru v reťazci

Porovnanie algoritmov pre vyhľadávanie vzoru v reťazci

Trieda použitá na analýzu a testovanie vybraných algoritmov

Trieda obsahuje najma premenné, do ktorých sa budú načítavať počty porovnaní. Samozrejme bude pre hodnotenie potrebné aj trvanie algoritmov pre rôzne dĺžky vzoru, reťazca a veľkosti použitej abecedy. 
 
//prehladavany retazec
class CRetazec
{
//statisticke premenne na analyzu roznych druhov porovnani
	int p_a_porovnani_;
	int p_b_porovnani_;
	int p_c_porovnani_;
	int p_d_porovnani_;
	char* retazec_;		//prehladavany retazec
	int velkost_;		//dlzka retazca bez ukoncovacieho znaku
public:
.
.
.
};