Grafy a tabuľky

Priemerné počty porovnaní vybraných implementácií

//Boyer-Mooreov algoritmus vyhladavania zadaneho vzoru "vzor" s poctom znakov "dlzka_v"
//v retazci "retazec" s poctom znakov "dlzka_r"
//funkcia vracia index prveho znaku najdeneho vzoru v retazci 
//(v pripade neuspechu vyhladavania vracia -1)
int CRetazec::najdi_BM(char *vzor, int dlzka) {
	int postupnost[MAX_DLZKA_VZORU];
	int vyskyt[MAX_VELKOST_ABECEDY];
 
	pre_postupnost(vzor, dlzka, postupnost);
	pre_vyskyt(vzor, dlzka, vyskyt);
 
	int j = 0;
	while ( ++p_a_porovnani_ && j <= velkost() - dlzka) {
		for (int i = dlzka - 1;  ++p_b_porovnani_ && i >= 0 &&  
			++p_b_porovnani_ && vzor[i] == retazec_[i + j]; i--);
		if ( ++p_b_porovnani_ && i  <  0) {
			return j;
			//j += postupnost[0];
		}
		else {
			++p_c_porovnani_;
			if (postupnost[i] >= vyskyt[retazec_[i + j]] - dlzka + 1 + i) 
				j+=postupnost[i];
			else j+=vyskyt[retazec_[i + j]] - dlzka + 1 + i;
		}
	}
	return -1;
}

//funkcia na vytvorenie pomocneho pola pre BM algoritmus
void CRetazec::pre_postupnost(char *vzor, int dlzka, int postupnost[]) {
    int suff[MAX_DLZKA_VZORU];
    suffixes(vzor, dlzka, suff);

    for (int i = 0; ++p_d_porovnani_ && i  <  dlzka; i++) postupnost[i] = dlzka;
    int j = 0;
    for (i = dlzka - 1; ++p_d_porovnani_ && i  >= -1; i--)
        if ((++p_d_porovnani_ && i == -1) || (++p_d_porovnani_ && suff[i] == i + 1))
            for (; ++p_d_porovnani_ && j  <  dlzka - 1 - i; j++)
                if (++p_d_porovnani_ && postupnost[j] == dlzka) 
                    postupnost[j] = dlzka - 1 - i;
    for (i = 0; ++p_d_porovnani_ && i  <= dlzka - 2; i++) 
        postupnost[dlzka - 1 - suff[i]] = dlzka - 1 - i;
}

//funkcia na vytvorenie pomocneho pola pre BM algoritmus
//(pre funkciu, ktora vytvara pomocne pole pre BM algoritmus)
void CRetazec::suffixes(char *vzor, int dlzka, int *suff) {
    int f;
    suff[dlzka - 1] = dlzka;
    int g = dlzka - 1;
    for (int i =dlzka - 2; ++p_d_porovnani_ &&  i >= 0; --i) {
        if ( ++p_d_porovnani_ && i  >  g && 
             ++p_d_porovnani_ && suff[i + dlzka - 1 - f]  <  i - g)
            suff[i] = suff[i + dlzka - 1 - f];
        else {
            if (++p_d_porovnani_ && i  <  g) g = i;
            f = i;
            while ( ++p_d_porovnani_ && g >= 0 &&
                    ++p_d_porovnani_ && vzor[g] == vzor[g + dlzka - 1 - f])
                g--;
            suff[i] = f - g;
        }
    }
}

//funkcia na vytvorenie pomocneho pola pre BM algoritmus
void CRetazec::pre_vyskyt(char *vzor, int dlzka, int vyskyt[]) {
   for (int i = 0; ++p_d_porovnani_ && i < MAX_VELKOST_ABECEDY; i++)
      vyskyt[i] = dlzka;
   for (i = 0; ++p_d_porovnani_ && i < dlzka - 1; i++)
      vyskyt[vzor[i]] = dlzka - i - 1;
}

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola