Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Napisz program, który obliczy i wyświetli tablicę prefikso‑sufiksów dla podanego wzorca. Swój algorytm przetestuj dla wzorca "AOAGDNMAOAGUIO".

Specyfikacja:

Dane:

tekst – wzorzec dla którego należy znaleźć tablicę prefikso‑sufiksów; ciąg znaków

Wynik:

Program wyświetla na wyjściu standardowym zawartość tablicaPrefiksoSufiksow - tablicy prefikso‑sufiksów dla podanego wzorca.

R10oWwoofR70r

Przykładowe rozwiązanie zadania:

#include <iostream>

using namespace std;

void generujTablicePrefiksoSufiksow(string wzorzec, int tablicaPrefiksoSufiksow[]) {
    int j = 0;
    int i = 1;
    
    tablicaPrefiksoSufiksow[0] = 0;
    while (i < wzorzec.size()) {
        if (wzorzec[i] == wzorzec[j]) {
            j++;
            tablicaPrefiksoSufiksow[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                tablicaPrefiksoSufiksow[i] = j;
                i++;
            }
        }
    }
}

int main() {
    string tekst = "AOAGDNMAOAGUIO";
    int tablicaPrefiksoSufiksow[tekst.size()] = {};
    
    generujTablicePrefiksoSufiksow(tekst, tablicaPrefiksoSufiksow);
    
    for (int i = 0; i < tekst.size(); i++) {
        cout << tablicaPrefiksoSufiksow[i] << " ";
    }

    return 0;
}

Ćwiczenie 2

Napisz program, który wyświetli wszystkie pozycje, na których został znaleziony podany wzorzec w tekście. Użyj algorytmu KMP. Swoje rozwiązanie przetestuj dla napisu "AOAGDNMAOAGUIO" i wzorca "AOAG".

Specyfikacja:

Dane:

napis – tekst do przeszukania; ciąg znaków
wzorzec – wzorzec, który należy odnaleźć; ciąg znaków

Wynik:

Program wypisuje na standardowe wyjście wszystkie indeksy w tablicy napis od których rozpoczyna się wzorzec z tablicy wzorzec, oddzielone spacjami.

R1APcabAxqWZt

Przykładowe rozwiązanie zadania:

#include <iostream>

using namespace std;

void generujTablicePrefiksoSufiksow(string wzorzec, int tablicaPrefiksoSufiksow[]) {
    int j = 0;
    int i = 1;
    
    tablicaPrefiksoSufiksow[0] = 0;
    while (i < wzorzec.size()) {
        if (wzorzec[i] == wzorzec[j]) {
            j++;
            tablicaPrefiksoSufiksow[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                tablicaPrefiksoSufiksow[i] = j;
                i++;
            }
        }
    }
}

void wyszukajKMP(string wzorzec, string napis) {
    int tablicaPrefiksoSufiksow[wzorzec.size()] = {};
    generujTablicePrefiksoSufiksow(wzorzec, tablicaPrefiksoSufiksow);
    
    int i = 0, j = 0;
    
    while (i < napis.size()) {
        if (wzorzec[j] == napis[i]) {
            j++; i++;
        }
        if (j == wzorzec.size()) {
            cout << (i - j) << " ";
            j = tablicaPrefiksoSufiksow[j - 1];
        }
        else if (i < napis.size() && wzorzec[j] != napis[i]) {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    string napis = "AOAGDNMAOAGUIO";
    string wzorzec = "AOAG";
    wyszukajKMP(wzorzec, napis);

    return 0;
}

Ćwiczenie 3

Napisz program, który sprawdzi, czy słowa - elementy tablicy slowa - występują w podanym ciągu znaków tekst. Dla każdego słowa wypisz w osobnej linii TAK, jeśli występuje w tekście choć raz, lub NIE w przeciwnym wypadku.

Specyfikacja:

Dane:

tekst – tekst do przeszukania; ciąg znaków
slowa – tablica wzorców, dla których należy określić czy występują w tekście co najmniej raz czy też nie; tablica ciągów znaków

Wynik:

Dla każdego elementu tablicy slowa, program wypisuje na standardowe wyjście TAK, jeżeli występuje ono w tekście w zmienniej tekst co najmniej raz lub NIE, w przeciwnym razie.

R1aQO4r5SQbQV

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. void generujTablicePrefiksoSufiksow otwórz nawias okrągły string wzorzec przecinek int tablicaPrefiksoSufiksow otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int j znak równości 0 średnik. Linia 7. int i znak równości 1 średnik. Linia 9. tablicaPrefiksoSufiksow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 0 średnik. Linia 10. while otwórz nawias okrągły i otwórz nawias ostrokątny wzorzec kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. if otwórz nawias okrągły wzorzec otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości wzorzec otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. j plus plus średnik. Linia 13. tablicaPrefiksoSufiksow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości j średnik. Linia 14. i plus plus średnik. Linia 15. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 16. if otwórz nawias okrągły j wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. j znak równości tablicaPrefiksoSufiksow otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 18. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 19. tablicaPrefiksoSufiksow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości j średnik. Linia 20. i plus plus średnik. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. int wyszukajKMP otwórz nawias okrągły string wzorzec przecinek string napis zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. int tablicaPrefiksoSufiksow otwórz nawias kwadratowy wzorzec kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias kwadratowy znak równości otwórz nawias klamrowy zamknij nawias klamrowy średnik. Linia 28. generujTablicePrefiksoSufiksow otwórz nawias okrągły wzorzec przecinek tablicaPrefiksoSufiksow zamknij nawias okrągły średnik. Linia 30. int i znak równości 0 przecinek j znak równości 0 średnik. Linia 32. while otwórz nawias okrągły i otwórz nawias ostrokątny napis kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. if otwórz nawias okrągły wzorzec otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości napis otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. j plus plus średnik i plus plus średnik. Linia 35. zamknij nawias klamrowy. Linia 36. if otwórz nawias okrągły j znak równości znak równości wzorzec kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. prawy ukośnik prawy ukośnik Funkcja zwraca pierwszy napotkany indeks. Linia 38. return otwórz nawias okrągły i minus j zamknij nawias okrągły średnik. Linia 39. j znak równości tablicaPrefiksoSufiksow otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 40. zamknij nawias klamrowy. Linia 41. else if otwórz nawias okrągły i otwórz nawias ostrokątny napis kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant wzorzec otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości napis otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. if otwórz nawias okrągły j wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 43. j znak równości tablicaPrefiksoSufiksow otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 44. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 45. i plus plus średnik. Linia 46. zamknij nawias klamrowy. Linia 47. zamknij nawias klamrowy. Linia 48. zamknij nawias klamrowy. Linia 49. return minus 1 średnik. Linia 50. zamknij nawias klamrowy. Linia 52. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. string slowa otwórz nawias kwadratowy 5 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 55. cudzysłów algorytm cudzysłów przecinek. Linia 56. cudzysłów metoda cudzysłów przecinek. Linia 57. cudzysłów mama cudzysłów przecinek. Linia 58. cudzysłów kajak cudzysłów przecinek. Linia 59. cudzysłów joanna cudzysłów. Linia 60. zamknij nawias klamrowy średnik. Linia 62. string tekst znak równości cudzysłów Lorem ipsum dolor sit amet enim kropka Etiam ullamcorper kropka Suspendisse a pellentesque dui przecinek non felis kropka Maecenas malesuada elit lectus felis przecinek joanna ultricies kropka Curabitur et ligula kropka Ut molestie a przecinek ultricies porta urna kropka Vestibulum metoda volutpat a przecinek convallis ac przecinek laoreet enim kropka Phasellus fermentum in przecinek dolor kropka Pellentesque facilisis kropka Nulla imperdiet sit amet magna kropka Vestibulum dapibus przecinek mauris nec malesuada fames ac turpis velit przecinek rhoncus eu przecinek luctus et interdum adipiscing wisi kropka Aliquam erat ac ipsum kropka Integer aliquam purus kropka Quisque lorem tortor fringilla sed przecinek vestibulum id przecinek eleifend justo vel bibendum sapien massa ac turpis faucibus orci luctus non przecinek consectetuer lobortis quis przecinek varius in przecinek purus kropka Integer ultrices posuere cubilia Curae przecinek Nulla ipsum dolor lacus przecinek suscipit adipiscing kropka Cum sociis natoque penatibus et ultrices volutpat kropka Nullam wisi ultricies a przecinek gravida vitae przecinek dapibus risus ante sodales lectus blandit eu przecinek tempor diam pede cursus vitae przecinek ultricies eu przecinek faucibus quis przecinek porttitor eros cursus lectus przecinek pellentesque eget przecinek bibendum a przecinek gravida ullamcorper quam kropka Nullam mama consectetuer kropka Quisque cursus et przecinek porttitor risus kropka Aliquam sem kropka In hendrerit nulla quam nunc przecinek accumsan congue kropka Lorem ipsum primis in nibh vel risus kropka Sed vel lectus kropka Ut sagittis przecinek ipsum dolor quam kropka cudzysłów średnik. Linia 64. int rezultat znak równości 0 średnik. Linia 65. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny 5 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 66. rezultat znak równości wyszukajKMP otwórz nawias okrągły slowa otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek tekst zamknij nawias okrągły średnik. Linia 67. if otwórz nawias okrągły rezultat zamknij nawias ostrokątny znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 68. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów TAK cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 69. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 70. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów NIE cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 71. zamknij nawias klamrowy. Linia 72. zamknij nawias klamrowy. Linia 74. return 0 średnik. Linia 75. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

void generujTablicePrefiksoSufiksow(string wzorzec, int tablicaPrefiksoSufiksow[]) {
    int j = 0;
    int i = 1;
    
    tablicaPrefiksoSufiksow[0] = 0;
    while (i < wzorzec.size()) {
        if (wzorzec[i] == wzorzec[j]) {
            j++;
            tablicaPrefiksoSufiksow[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                tablicaPrefiksoSufiksow[i] = j;
                i++;
            }
        }
    }
}

int wyszukajKMP(string wzorzec, string napis) {
    int tablicaPrefiksoSufiksow[wzorzec.size()] = {};
    generujTablicePrefiksoSufiksow(wzorzec, tablicaPrefiksoSufiksow);
    
    int i = 0, j = 0;
    
    while (i < napis.size()) {
        if (wzorzec[j] == napis[i]) {
            j++; i++;
        }
        if (j == wzorzec.size()) {
            // Funkcja zwraca pierwszy napotkany indeks
            return (i - j);
            j = tablicaPrefiksoSufiksow[j - 1];
        }
        else if (i < napis.size() && wzorzec[j] != napis[i]) {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

int main() {

    string slowa[5] = {
        "algorytm",
        "metoda",
        "mama",
        "kajak",
        "joanna"
    };

    string tekst = "Lorem ipsum dolor sit amet enim. Etiam ullamcorper. Suspendisse a pellentesque dui, non felis. Maecenas malesuada elit lectus felis, joanna ultricies. Curabitur et ligula. Ut molestie a, ultricies porta urna. Vestibulum metoda volutpat a, convallis ac, laoreet enim. Phasellus fermentum in, dolor. Pellentesque facilisis. Nulla imperdiet sit amet magna. Vestibulum dapibus, mauris nec malesuada fames ac turpis velit, rhoncus eu, luctus et interdum adipiscing wisi. Aliquam erat ac ipsum. Integer aliquam purus. Quisque lorem tortor fringilla sed, vestibulum id, eleifend justo vel bibendum sapien massa ac turpis faucibus orci luctus non, consectetuer lobortis quis, varius in, purus. Integer ultrices posuere cubilia Curae, Nulla ipsum dolor lacus, suscipit adipiscing. Cum sociis natoque penatibus et ultrices volutpat. Nullam wisi ultricies a, gravida vitae, dapibus risus ante sodales lectus blandit eu, tempor diam pede cursus vitae, ultricies eu, faucibus quis, porttitor eros cursus lectus, pellentesque eget, bibendum a, gravida ullamcorper quam. Nullam mama consectetuer. Quisque cursus et, porttitor risus. Aliquam sem. In hendrerit nulla quam nunc, accumsan congue. Lorem ipsum primis in nibh vel risus. Sed vel lectus. Ut sagittis, ipsum dolor quam.";

    int rezultat = 0;
    for (int i = 0; i < 5; i++) {
        rezultat = wyszukajKMP(slowa[i], tekst);
        if (rezultat >= 0) {
            cout << "TAK" << endl;
        } else {
            cout << "NIE" << endl;
        }
    }

    return 0;
}

Przeczytaj

Dla nauczyciela