Program realizujący algorytm Knutha-Morrisa-Pratta

//Program napisany w C++

#include

#include

using namespace std;

char* tekst = new char[1000000];

char* wzorzec = new char[1000000];

int* KMP;

int dlugosc;

void liczKMP(char* wzorzec, int* KMP, int dlugoscwz){

KMP[1] = 0;

int i = 0 ;

for (int j = 1; j

while (i>0 && wzorzec[j+1]!=wzorzec[i+1]) {

i = KMP[i];

}

if (wzorzec[j+1] == wzorzec[i+1]) i++;

KMP[j+1] = i;

}

}

void wypisz(int numer){//wypisuje pozycję na której był wzorzec

printf("%d ", numer);

}

void funkcjaKMP(char* wzorzec, int* KMP, int dlugoscwz){

bool cosznaleziono = false;

liczKMP(wzorzec, KMP, dlugoscwz);

// cout << "W funkcji funkcjaKMP()"<

int j = 0;

for (int i = 1; i<=dlugosc; i++){

while ((j>0)&& (wzorzec[j+1]!= tekst[i])){

j = KMP[j];

} 

if (tekst[i]==wzorzec[j+1]) j++;

if (j==dlugoscwz){

cosznaleziono = true;

wypisz(i-j+1);

j = KMP[j]; //szukamy dalej

}

} 

if (!cosznaleziono) printf("BRAK");

else printf("");

}

int main (){

printf("Podaj liczbę prób");

char cos;

int proby;

int dlugoscwz = 0;

scanf("%d",&proby);

scanf("%c",&cos); //wylapuje znak konca linii

for (int j = 0; j

dlugoscwz = 0;

dlugosc = 0;

for (int i = 1; ; i++){

dlugosc++;

scanf ("%c", &tekst[i]);

if (tekst[i]==''){ //napotyka znak konca linii

dlugosc--;

break;

} 

}

for (int i = 1; ; i++){

dlugoscwz++;

scanf("%c", &wzorzec[i]);

if (wzorzec[i]==''){ //napotyka znak konca linii

dlugoscwz--;

break;

} 

}

KMP = new int[dlugoscwz+1];

funkcjaKMP(wzorzec, KMP, dlugoscwz);

delete[] KMP;

}

return 0; 

}