Przeczytaj

Podsumowanie informacji o algorytmie KMP w języku C++

W omawianym przykładzie będziemy posługiwać się następującymi zmiennymi:

tekst – ciąg znaków przechowujący przeszukiwany tekst,
znajdz – ciąg znaków przechowujący wyszukiwany tekst,
dopasowania – tablica częściowych dopasowań o rozmiarze równym liczbie znaków zapisanych w zmiennej znajdz.

Funkcja tworząca tablicę częściowych dopasowań

Krok 1

Zapiszmy nagłówek naszej funkcji:

void – funkcja nic nie zwraca, tylko wypełnia tablicę;

string znajdz – łańcuch znaków, na którym będziemy operować;

int dopasowania[] – tablica dopasowań.

void stworzTablice(string znajdz, int dopasowania[])

Krok 2

Deklarujemy zmienną pomocniczą a.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;
}

Krok 3

W tablicy dopasowań wartość komórki zapisanej pod indeksem zero ustawiamy na 0.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
}

Krok 4

Deklarujemy zmienną pomocniczą i, a następnie ustawiamy jej wartość na 1.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;
}

Krok 5

Tworzymy pętlę, która będzie się wykonywała, dopóki zmienna i nie osiągnie wartości równej liczbie znaków w łańcuchu znajdz. Do pobrania długości tekstu użyj funkcji size()Funkcja size()size().

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;

    while(i < znajdz.size())
    {
    
    }
}

Krok 6

Sprawdzamy, czy znak zapisany pod indeksem i jest taki sam, jak znak zapisany pod indeksem a, czyli czy możemy rozszerzyć zakres długości prefiksu i sufiksu (pamiętajmy, że zgodnie z założeniem algorytmu prefiks zaczynający się od indeksu 0 i kończący się na indeksie $a-1$ jest identyczny z sufiksem o długości $a$ , kończącym się na pozycji $i-1$ ).

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;

    while(i < znajdz.size())
    {
        if(znajdz[i] == znajdz[a])
        {

        }   
    }
}

Krok 7

Jeśli tak jest, zwiększamy wartość zmiennej a o jeden, ustawiamy komórkę w tablicy dopasowania o indeksie i na wartość zmiennej a, następnie zwiększamy wartość zmiennej i o 1.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;

    while(i < znajdz.size())
    {
        if(znajdz[i] == znajdz[a])
        {
            a++;
            dopasowania[i] = a;
            i++;
        }   
    }
}

Krok 8

Jeśli tak nie jest, sprawdzamy, czy a jest różne od zera.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;

    while(i < znajdz.size())
    {
        if(znajdz[i] == znajdz[a])
        {
            a++;
            dopasowania[i] = a;
            i++;
        }
        else
        {
            if(a != 0)
            
        }
     }   
}

Krok 9

Jeśli tak, przypisujemy zmiennej a wartość zmiennej zapisanej w tablicy dopasowania pod indeksem a - 1.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;

    while(i < znajdz.size())
    {
        if(znajdz[i] == znajdz[a])
        {
            a++;
            dopasowania[i] = a;
            i++;
        }
        else
        {
            if(a != 0)
                a = dopasowania[a-1];
        }
     }   
}

Krok 10

W przeciwnym razie przypisujemy zmiennej zapisanej pod indeksem i w tablicy dopasowania wartość zero, a następnie zwiększamy wartość zmiennej i o 1.

void stworzTablice(string znajdz, int dopasowania[])
{
    int a = 0;

    dopasowania[0] = 0;
    int i = 1;

    while(i < znajdz.size())
    {
        if(znajdz[i] == znajdz[a])
        {
            a++;
            dopasowania[i] = a;
            i++;
        }
        else
        {
            if(a != 0)
                a = dopasowania[a-1];
            else
            {
                dopasowania[i] = 0;
                i++;
            }     	
    }
}

Wyszukiwanie wzorca w tekście

Napisz właściwą funkcję algorytmu, która będzie wykorzystywała zapisaną funkcję tworzenia tablicy częściowych dopasowań.

Krok 1

Zapiszmy nagłówek funkcji.

void KnuthMorrisPratt(string znajdz, string tekst)
{
    
}

void – funkcja nic nie zwraca, tylko wypełnia tablicę;

string znajdz – łańcuch znaków, który przechowuje wyszukiwany wzorzecwzorzecwzorzec;

string tekst – łańcuch znaków przechowujący tekst, w którym szukamy wzorca.

Krok 2

Deklarujemy tablicę o liczbie komórek równej liczbie znaków we wzorcu. Będzie to tablica częściowych dopasowań.

void KnuthMorrisPratt(string znajdz, string tekst)
{
    int dopasowania[znajdz.size()];
}

Krok 3

Wywołujemy funkcję stworzTablice(), którą wcześniej zapisaliśmy, podając jako jej parametry łańcuch znaków znajdz oraz tablicę dopasowania.

void KnuthMorrisPratt(string znajdz, string tekst)
{
    int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
}

Krok 4

Deklarujemy zmienne i oraz j i przypisujemy im wartości równe 0.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
}

Krok 5

Tworzymy pętlę wykonującą się dopóki wartość zmiennej i będzie mniejsza od liczby znaków w przeszukiwanym tekście.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {

    }
}

Krok 6

Sprawdzamy, czy znak zapisany w łańcuchu znajdz w komórce o indeksie j jest taki sam, jak znak zapisany w łańcuchu tekst w komórce o indeksie i.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {

        }
    }
}

Krok 7

Jeśli tak jest, inkrementujemy zmienną i oraz zmienną j.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }
    }
}

Krok 8

Sprawdzamy, czy zmienna j jest równa liczbie znaków w łańcuchu znajdz.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }

        if (j == znajdz.size())
        {

        }   
    }   
}

Krok 9

Jeśli tak jest, to wyświetlamy odpowiedni komunikat o odnalezieniu wzorca na pozycji i - j oraz ustawiamy wartość zmiennej j na wartość równą zmiennej zapisanej w tablicy dopasowania pod indeksem j - 1.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }

        if (j == znajdz.size())
        {
            cout << "Znaleziono wzor na pozycji: " << i - j << endl;
            j = dopasowania[j - 1];
        }  
    }   
}

Krok 10

Jeśli warunek w poprzednim kroku nie jest spełniony, sprawdzamy, czy zmienna i jest mniejsza od liczby znaków w przeszukiwanym tekście i jednocześnie, czy znak zapisany w łańcuchu znajdz jest różny od znaku zapisanego w łańcuchu tekst pod indeksem i.

Linia 1. void KnuthMorrisPratt otwórz nawias okrągły string znajdz przecinek string tekst zamknij nawias okrągły. Linia 2. otwórz nawias klamrowy. Linia 3. int dopasowania otwórz nawias kwadratowy znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias kwadratowy średnik. Linia 4. stworzTablice otwórz nawias okrągły znajdz przecinek dopasowania zamknij nawias okrągły średnik. Linia 5. int i znak równości 0 średnik. Linia 6. int j znak równości 0 średnik. Linia 7. while otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy. Linia 11. i plus plus średnik. Linia 12. j plus plus średnik. Linia 13. zamknij nawias klamrowy. Linia 15. if otwórz nawias okrągły j znak równości znak równości znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Znaleziono wzor na pozycji dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i minus j otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 18. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 19. zamknij nawias klamrowy. Linia 20. else if otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 21. otwórz nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }

        if (j == znajdz.size())
        {
            cout << "Znaleziono wzor na pozycji: " << i - j << endl;
            j = dopasowania[j - 1];
        }
        else if (i < tekst.size() && znajdz[j] != tekst[i])
        {

        }
    }
}

Krok 11

Jeśli tak, sprawdzamy, czy zmienna j jest różna od zera.

Linia 1. void KnuthMorrisPratt otwórz nawias okrągły string znajdz przecinek string tekst zamknij nawias okrągły. Linia 2. otwórz nawias klamrowy. Linia 3. int dopasowania otwórz nawias kwadratowy znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias kwadratowy średnik. Linia 4. stworzTablice otwórz nawias okrągły znajdz przecinek dopasowania zamknij nawias okrągły średnik. Linia 5. int i znak równości 0 średnik. Linia 6. int j znak równości 0 średnik. Linia 7. while otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy. Linia 11. i plus plus średnik. Linia 12. j plus plus średnik. Linia 13. zamknij nawias klamrowy. Linia 15. if otwórz nawias okrągły j znak równości znak równości znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Znaleziono wzor na pozycji dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i minus j otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 18. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 19. zamknij nawias klamrowy. Linia 20. else if otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 21. otwórz nawias klamrowy. Linia 22. if otwórz nawias okrągły j wykrzyknik znak równości 0 zamknij nawias okrągły. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }

        if (j == znajdz.size())
        {
            cout << "Znaleziono wzor na pozycji: " << i - j << endl;
            j = dopasowania[j - 1];
        }
        else if (i < tekst.size() && znajdz[j] != tekst[i])
        {
            if (j != 0)
        }
    }
}

Krok 12

Jeśli tak, ustawiamy wartość zmiennej j na wartość równą wartości zapisanej w tablicy dopasowania, pod indeksem j - 1.

Linia 1. void KnuthMorrisPratt otwórz nawias okrągły string znajdz przecinek string tekst zamknij nawias okrągły. Linia 2. otwórz nawias klamrowy. Linia 3. int dopasowania otwórz nawias kwadratowy znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias kwadratowy średnik. Linia 4. stworzTablice otwórz nawias okrągły znajdz przecinek dopasowania zamknij nawias okrągły średnik. Linia 5. int i znak równości 0 średnik. Linia 6. int j znak równości 0 średnik. Linia 7. while otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy. Linia 11. i plus plus średnik. Linia 12. j plus plus średnik. Linia 13. zamknij nawias klamrowy. Linia 15. if otwórz nawias okrągły j znak równości znak równości znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Znaleziono wzor na pozycji dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i minus j otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 18. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 19. zamknij nawias klamrowy. Linia 20. else if otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 21. otwórz nawias klamrowy. Linia 22. if otwórz nawias okrągły j wykrzyknik znak równości 0 zamknij nawias okrągły. Linia 23. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }

        if (j == znajdz.size())
        {
            cout << "Znaleziono wzor na pozycji: " << i - j << endl;
            j = dopasowania[j - 1];
        }
        else if (i < tekst.size() && znajdz[j] != tekst[i])
        {
            if (j != 0)
                j = dopasowania[j - 1];
        }
    }
}

Krok 13

W przeciwnym razie inkrementujemy zmienną i.

Linia 1. void KnuthMorrisPratt otwórz nawias okrągły string znajdz przecinek string tekst zamknij nawias okrągły. Linia 2. otwórz nawias klamrowy. Linia 3. int dopasowania otwórz nawias kwadratowy znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias kwadratowy średnik. Linia 4. stworzTablice otwórz nawias okrągły znajdz przecinek dopasowania zamknij nawias okrągły średnik. Linia 5. int i znak równości 0 średnik. Linia 6. int j znak równości 0 średnik. Linia 7. while otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy. Linia 11. i plus plus średnik. Linia 12. j plus plus średnik. Linia 13. zamknij nawias klamrowy. Linia 15. if otwórz nawias okrągły j znak równości znak równości znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Znaleziono wzor na pozycji dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i minus j otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 18. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 19. zamknij nawias klamrowy. Linia 20. else if otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 21. otwórz nawias klamrowy. Linia 22. if otwórz nawias okrągły j wykrzyknik znak równości 0 zamknij nawias okrągły. Linia 23. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 24. else. Linia 25. i plus plus średnik. Linia 26. zamknij nawias klamrowy. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy.

void KnuthMorrisPratt(string znajdz, string tekst)
{
	int dopasowania[znajdz.size()];
	stworzTablice(znajdz, dopasowania);
	int i = 0;
	int j = 0;
    while (i < tekst.size())
    {
        if (znajdz[j] == tekst[i])
        {
            i++;
            j++;
        }

        if (j == znajdz.size())
        {
            cout << "Znaleziono wzor na pozycji: " << i - j << endl;
            j = dopasowania[j - 1];
        }
        else if (i < tekst.size() && znajdz[j] != tekst[i])
        {
            if (j != 0)
                j = dopasowania[j - 1];
            else
                i++;
        }
    }
}

Całkowita implementacja w języku C++

Cały algorytm KMP w postaci obu funkcji prezentuje się następująco:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. void stworzTablice otwórz nawias okrągły string znajdz przecinek int dopasowania otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy. Linia 8. int a znak równości 0 średnik. Linia 10. dopasowania otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 0 średnik. Linia 11. unsigned int i znak równości 1 średnik. Linia 13. while otwórz nawias okrągły i otwórz nawias ostrokątny znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 14. otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły znajdz otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości znajdz otwórz nawias kwadratowy a zamknij nawias kwadratowy zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. a plus plus średnik. Linia 18. dopasowania otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości a średnik. Linia 19. i plus plus średnik. Linia 20. zamknij nawias klamrowy. Linia 21. else. Linia 22. otwórz nawias klamrowy. Linia 23. if otwórz nawias okrągły a wykrzyknik znak równości 0 zamknij nawias okrągły. Linia 24. a znak równości dopasowania otwórz nawias kwadratowy a minus 1 zamknij nawias kwadratowy średnik. Linia 25. else. Linia 26. otwórz nawias klamrowy. Linia 27. dopasowania otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 28. i plus plus średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 35. void KnuthMorrisPratt otwórz nawias okrągły string znajdz przecinek string tekst zamknij nawias okrągły. Linia 36. otwórz nawias klamrowy. Linia 37. int dopasowania otwórz nawias kwadratowy znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias kwadratowy średnik. Linia 38. stworzTablice otwórz nawias okrągły znajdz przecinek dopasowania zamknij nawias okrągły średnik. Linia 40. unsigned int i znak równości 0 średnik. Linia 41. unsigned int j znak równości 0 średnik. Linia 43. while otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 44. otwórz nawias klamrowy. Linia 45. if otwórz nawias okrągły znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 46. otwórz nawias klamrowy. Linia 47. i plus plus średnik. Linia 48. j plus plus średnik. Linia 49. zamknij nawias klamrowy. Linia 51. if otwórz nawias okrągły j znak równości znak równości znajdz kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 52. otwórz nawias klamrowy. Linia 53. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Znaleziono wzor na pozycji dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i minus j otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 54. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 55. zamknij nawias klamrowy. Linia 56. else if otwórz nawias okrągły i otwórz nawias ostrokątny tekst kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant znajdz otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości tekst otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 57. otwórz nawias klamrowy. Linia 58. if otwórz nawias okrągły j wykrzyknik znak równości 0 zamknij nawias okrągły. Linia 59. j znak równości dopasowania otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 60. else. Linia 61. i plus plus średnik. Linia 62. zamknij nawias klamrowy. Linia 63. zamknij nawias klamrowy. Linia 64. zamknij nawias klamrowy. Linia 66. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 67. KnuthMorrisPratt otwórz nawias okrągły cudzysłów HAA cudzysłów przecinek cudzysłów AGHAAGAAHAA cudzysłów zamknij nawias okrągły średnik. Linia 68. KnuthMorrisPratt otwórz nawias okrągły cudzysłów DAA cudzysłów przecinek cudzysłów ADAADAADAADA cudzysłów zamknij nawias okrągły średnik. Linia 69. KnuthMorrisPratt otwórz nawias okrągły cudzysłów kot cudzysłów przecinek cudzysłów ala ma kota kot ma ale cudzysłów zamknij nawias okrągły średnik. Linia 71. return 0 średnik. Linia 72. zamknij nawias klamrowy.

 #include <iostream>
 #include <string>
 
 using namespace std;
 
 void stworzTablice(string znajdz, int dopasowania[])
 {
 	int a = 0;
 
 	dopasowania[0] = 0;
 	unsigned int i = 1;
 
 	while(i < znajdz.size())
 	{
 		if(znajdz[i] == znajdz[a])
 		{
 			a++;
 			dopasowania[i] = a;
 			i++;
 		}
 		else
 		{
 			if(a != 0)
 				a = dopasowania[a-1];
 			else
 			{
 				dopasowania[i] = 0;
 				i++;
 			}
 		}
 	}
 }
 
 
 void KnuthMorrisPratt(string znajdz, string tekst)
 {
 	int dopasowania[znajdz.size()];
 	stworzTablice(znajdz, dopasowania);
 	
 	unsigned int i = 0;
 	unsigned int j = 0;
 	
 	while(i < tekst.size())
 	{
 		if(znajdz[j] == tekst[i])
 		{
 			i++;
 			j++;
 		}
 		
 		if(j == znajdz.size())
 		{
 			cout<<"Znaleziono wzor na pozycji: "<<i-j<<endl;
 			j = dopasowania[j-1];
 		}
 		else if(i < tekst.size() && znajdz[j] != tekst[i])
 		{
 			if(j != 0)
 				j = dopasowania[j-1];
 			else
 				i++;
 		}
 	}
 }
 
 int main() {
 	KnuthMorrisPratt("HAA", "AGHAAGAAHAA");
 	KnuthMorrisPratt("DAA", "ADAADAADAADA");
 	KnuthMorrisPratt("kot", "ala ma kota kot ma ale");
 	
 	return 0;
 }

Słownik

funkcja size()

funkcja w miejscu wywołania zwraca liczbę znaków w łańcuchu znaków (string); przykładowe wywołanie: tekst.size()

wzorzec

ciąg znaków, którego wystąpień poszukujemy w tekście

Film samouczek

Sprawdź się

Podsumowanie informacji o algorytmie KMP w języku C++

Funkcja tworząca tablicę częściowych dopasowań

Krok 1

Krok 2

Krok 3

Krok 4

Krok 5

Krok 6

Krok 7

Krok 8

Krok 9

Krok 10

Wyszukiwanie wzorca w tekście

Krok 1

Krok 2

Krok 3

Krok 4

Krok 5

Krok 6

Krok 7

Krok 8

Krok 9

Krok 10

Krok 11

Krok 12

Krok 13

Całkowita implementacja w języku C++

Słownik