Implementácie

//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 najdi_BM(char *vzor, int dlzka_v, char* retazec, int dlzka_r) {
	int postupnost[MAX_DLZKA_VZORU];
	int vyskyt[MAX_VELKOST_ABECEDY];
 
	pre_postupnost(vzor, dlzka_v, postupnost);
	pre_vyskyt(vzor, dlzka_v, vyskyt);
 
	int j = 0;
	while (j <= dlzka_r - dlzka_v) {
		for (int i = dlzka_v - 1; i  >= 0 && vzor[i] == retazec[i + j]; i--);
		if (i < 0) {
			return j;
			//j += postupnost[0];
		}
		else if (postupnost[i] >= vyskyt[retazec[i + j]] - dlzka_v + 1 + i) 
			j+=postupnost[i];
		else j+=vyskyt[retazec[i + j]] - dlzka_v + 1 + i;
	}
	return -1;
}

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

    for (int i = 0; i  <  dlzka; i++) postupnost[i] = dlzka;
    int j = 0;
    for (i = dlzka - 1; i >= -1; i--)
        if (i == -1 || suff[i] == i + 1)
            for (; j < dlzka - 1 - i; j++)
                if (postupnost[j] == dlzka) postupnost[j] = dlzka - 1 - i;
    for (i = 0; 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 suffixes(char *vzor, int dlzka, int *suff) {
    int f;
    suff[dlzka - 1] = dlzka;
    int g = dlzka - 1;
    for (int i=dlzka - 2; i >= 0; --i) {
        if ( i > g && suff[i + dlzka - 1 - f]  < i - g)
            suff[i] = suff[i + dlzka - 1 - f];
        else {
            if (i < g) g = i;
            f = i;
            while (g  >= 0 && vzor[g] == vzor[g + dlzka - 1 - f]) g--;
            suff[i] = f - g;
        }
    }
}

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