Implementácie

//Knuth-Morris-Prattov 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_KMP(char* vzor, int dlzka_v, char* retazec, int dlzka_r){
	if (dlzka_v > MAX_DLZKA_VZORU) return -2;
	int postupnost[MAX_DLZKA_VZORU+1];
	pre(vzor, dlzka_v, &postupnost[0]);

	int i=0;
	int j=0;
	while (j < dlzka_r) {
		if (vzor[i] == retazec[j]) {
			if (i == dlzka_v-1) {
				return (j-dlzka_v+1);
				//i=postupnost[i];
			}
			else {i++; j++;}
		}
		else if (postupnost[i] == -1) {i=0; j++;}
		else i=postupnost[i];
	}
	return -1;
}

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