Grafy a tabuľky

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

//Knuth-Morris-Prattov algoritmus vyhladavania zadaneho vzoru "vzor" s poctom znakov "dlzka"
//funkcia vracia index prveho znaku najdeneho vzoru v retazci 
//(v pripade neuspechu vyhladavania vracia -1)
int CRetazec::najdi_KMP(char* vzor, int dlzka){
	if (dlzka > MAX_DLZKA_VZORU) return -2;
	int postupnost[MAX_DLZKA_VZORU+1];
	pre(vzor, dlzka, &postupnost[0]);

	int i=0;
	int j=0;
	while (++p_a_porovnani_ && j < velkost_) {
		if (++p_b_porovnani_ && vzor[i] == retazec_[j]) {
			if (++p_b_porovnani_ && i == dlzka-1) {
				return (j-dlzka+1); 
				//i=postupnost[i];
			}
			else {i++; j++;}
		}
		else if (++p_c_porovnani_ && postupnost[i] == -1) {i=0; j++;}
		else i=postupnost[i];
	}
	return -1;
}

//funkcia na vytvorenie pomocneho pola pre KMP algoritmus
void CRetazec::pre(char* vzor, int dlzka, int* postupnost){
    int i = 0;
    int j = postupnost[0] = -1;
    while (++p_d_porovnani_ && i < dlzka) {
        while (++p_d_porovnani_ && j > -1 && ++p_d_porovnani_ && vzor[i] != vzor[j]) 
            { j = postupnost[j]; }
        i++;
        j++;
        if (++p_d_porovnani_ && vzor[i] == vzor[j]) postupnost[i] = postupnost[j];
        else postupnost[i] = j;
    }
}

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