Strefa wyzwań - I_P_W14_M16 Algorytm Knutha‑Morrisa‑Pratta

RmtGf1Gvh45gA

Już wiesz

Jak wygląda proces wyszukiwania wzorców w tekście, w szczególności zagadnienie wykorzystania metody Knutha‑Morrisa‑Pratta.
POtrafisz krok po kroku proces, który doprowadzi cię do odszukania wzorca w tekście.
Jak zaimplementować algorytm tworzenia tablicy częściowych dopasowań w języku Java.
Jak zaimplementować algorytm wyszukiwania wzorców metodą Knutha‑Morrisa‑Pratta w języku Java.

Teraz czas, aby sprawdzić wiedzę i umiejętności w praktyce.

Ćwiczenie 1

W programie zdefiniowano zmienną slowo. Twoim zadaniem jest zbudowanie dla niej tablicy częściowych dopasowań metodą MP. W jednej linii wypisz tablicę dopasowań dla zmiennej, oddzielając jej elementy przecinkiem oraz spacją.

Przetestuj program dla zmiennej slowo = "tata".

Przypomnienie z poprzednich e‑materiałów:

W przeciwieństwie do metody KMP, metoda MP zakłada, że w momencie, gdy element występujący po znalezionym prefikso‑sufiksie będzie taki sam jak występujący po sufiksie, zamiast wpisywać wartość z tablicy na pozycji równej szerokości prefikso‑sufiksu, będziemy wpisywać do tablicy szerokość prefikso‑sufiksu.

Specyfikacja problemu:

Dane:

slowo – zmienna typu String

Wynik:

Program tworzy tablicę częściowych dopasowań metodą MP.

Przykładowe wyjście (slowo = "mama"):

-1, 0, 0, 1, 2

RWHhL6hsncCjW

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. static int otwórz nawias kwadratowy zamknij nawias kwadratowy budowaTablicyMP otwórz nawias okrągły String wzorzec zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int rozmiarT znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły plus 1 średnik. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy T znak równości new int otwórz nawias kwadratowy rozmiarT zamknij nawias kwadratowy średnik. Linia 5. int poz znak równości minus 1 średnik. Linia 6. T otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 8. prawy ukośnik prawy ukośnik dla każdego kolejnego prefiksu wzorca. Linia 9. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny rozmiarT średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. prawy ukośnik prawy ukośnik dopóki możesz znaleźć dłuższy prefikso minus sufiks. Linia 11. while otwórz nawias okrągły poz zamknij nawias ostrokątny minus 1 ampersant ampersant wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły i minus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. poz znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 13. zamknij nawias klamrowy. Linia 14. plus plus poz średnik. Linia 16. prawy ukośnik prawy ukośnik zapisz szerokość znalezionego prefikso minus sufiksu. Linia 17. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości poz średnik. Linia 18. zamknij nawias klamrowy. Linia 20. return T średnik. Linia 21. zamknij nawias klamrowy. Linia 22. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. String slowo znak równości cudzysłów tata cudzysłów średnik. Linia 24. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablicaDopasowan znak równości budowaTablicyMP otwórz nawias okrągły slowo zamknij nawias okrągły średnik. Linia 26. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tablicaDopasowan kropka length średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. System kropka out kropka print otwórz nawias okrągły tablicaDopasowan otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 28. if otwórz nawias okrągły i wykrzyknik znak równości tablicaDopasowan kropka length minus 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. System kropka out kropka print otwórz nawias okrągły cudzysłów przecinek cudzysłów zamknij nawias okrągły średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy.

public class Main {	
	static int[] budowaTablicyMP(String wzorzec) {
    	int rozmiarT = wzorzec.length() + 1;
    	int[] T = new int[rozmiarT];
    	int poz = -1;
    	T[0] = -1;

    	// dla każdego kolejnego prefiksu wzorca
    	for (int i = 1; i < rozmiarT; ++i) {
        	// dopóki możesz znaleźć dłuższy prefikso-sufiks
        	while(poz > -1 && wzorzec.charAt(poz) != wzorzec.charAt(i - 1)) {
            	poz = T[poz];
        	}
        	++poz;

        	// zapisz szerokość znalezionego prefikso-sufiksu
        	T[i] = poz;
    	}

    	return T;
	}
    public static void main(String[] args) {
        String slowo = "tata";
        int[] tablicaDopasowan = budowaTablicyMP(slowo);

        for (int i = 0; i < tablicaDopasowan.length; ++i) {
            System.out.print(tablicaDopasowan[i]);
            if (i != tablicaDopasowan.length - 1) {
                System.out.print(", ");
            }
    	}
	}
}

Ćwiczenie 2

W programie zdefiniowano tablicę zawierającą n słów. Twoim zadaniem jest zbudowanie dla nich tablic częściowych dopasowań metodą KMP. Dla każdego słowa wypisz w osobnej linii jego tablicę dopasowań, oddzielając jej elementy przecinkiem oraz spacją. Przetestuj działanie programu dla następującej tablicy:

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

Specyfikacja problemu:

Dane:

slowa – tablica składająca się z n elementów (łańcuchów znaków)
n – liczba naturalna dodatnia

Wynik:

Program tworzy tablicę częściowych dopasowań metodą KMP.

Przykładowe wyjście (slowa = {"cogito", "ergo", "sum", "carpe", "diem"):

-1, 0, 0, 0, 0, 0, 0
-1, 0, 0, 0, 0
-1, 0, 0, 0
-1, 0, 0, 0, 0, 0
-1, 0, 0, 0, 0

RnLnFAWBAtAly

public class Main {
    static int[] budowaTablicyKMP(String wzorzec) {
        int rozmiarT = wzorzec.length() + 1;
        int[] T = new int[rozmiarT];
        int poz = -1;
        T[0] = -1;

        // dla każdego kolejnego prefiksu wzorca
        for (int i = 1; i < rozmiarT; ++i) {
            // dopóki możesz znaleźć dłuższy prefikso-sufiks
            while(poz > -1 && wzorzec.charAt(poz) != wzorzec.charAt(i - 1)) {
                poz = T[poz];
            }
            ++poz;

            // jeżeli element występujący po znalezionym
            // prefikso-sufiksie jest taki sam jak po prefiksie
            if (i == rozmiarT - 1 || wzorzec.charAt(i) != wzorzec.charAt(poz)) {
                // zapisz szerokość znalezionego prefikso-sufiksu
                T[i] = poz;
            }
            else {
                // kolejny element tablicy będzie tym samym,
                // co element na pozycji równej szerokości
                // prefikso-sufiksu
                T[i] = T[poz];
            }
        }

        return T;
    }

    public static void main(String[] args) {
        String[] slowa = {
                "algorytm",
                "metoda",
                "mama",
                "kajak",
                "joanna"
        };

        for (int i = 0; i < slowa.length; ++i) {
            int[] tablicaDopasowan = budowaTablicyKMP(slowa[i]);

            for (int j = 0; j < tablicaDopasowan.length; ++j) {
                System.out.print(tablicaDopasowan[j]);
                if (j != tablicaDopasowan.length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print('\n');
        }
    }
}

Ćwiczenie 3

Do programu z ćwiczenia 2 dodano ciąg znaków: tekst. Korzystając z uprzednio utworzonych tablic częściowych dopasowań, sprawdź, które elementy tablicy slowa występują w łańcuchu znaków tekst. Dla każdego słowa w osobnej linii wypisz TAK, jeśli pojawia się w tekście lub NIE – w przeciwnym wypadku.

Specyfikacja problemu:

Dane:

slowa – tablica składająca się z n elementów (łańcuchów znaków)
n – liczba naturalna dodatnia
tekst – ciąg znaków o długości m
m – liczba naturalna dodatnia

Wynik:

Program dla każdego słowa w osobnej linii wypisuje komunikat TAK lub NIE (w zależności od tego, czy pojawia się w tekście).

Rbjp1R2zhkl0e

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. static int otwórz nawias kwadratowy zamknij nawias kwadratowy budowaTablicyKMP otwórz nawias okrągły String wzorzec zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int rozmiarT znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły plus 1 średnik. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy T znak równości new int otwórz nawias kwadratowy rozmiarT zamknij nawias kwadratowy średnik. Linia 5. int poz znak równości minus 1 średnik. Linia 6. T otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 8. prawy ukośnik prawy ukośnik dla każdego kolejnego prefiksu wzorca. Linia 9. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny rozmiarT średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. prawy ukośnik prawy ukośnik dopóki możesz znaleźć dłuższy prefikso minus sufiks. Linia 11. while otwórz nawias okrągły poz zamknij nawias ostrokątny minus 1 ampersant ampersant wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły i minus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. poz znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 13. zamknij nawias klamrowy. Linia 14. plus plus poz średnik. Linia 16. prawy ukośnik prawy ukośnik jeżeli element występujący po znalezionym. Linia 17. prawy ukośnik prawy ukośnik prefikso minus sufiksie jest taki sam jak po prefiksie. Linia 18. if otwórz nawias okrągły i znak równości znak równości rozmiarT minus 1 kreska pionowa kreska pionowa wzorzec kropka charAt otwórz nawias okrągły i zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. prawy ukośnik prawy ukośnik zapisz szerokość znalezionego prefikso minus sufiksu. Linia 20. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości poz średnik. Linia 21. zamknij nawias klamrowy. Linia 22. else otwórz nawias klamrowy. Linia 23. prawy ukośnik prawy ukośnik kolejny element tablicy będzie tym samym przecinek. Linia 24. prawy ukośnik prawy ukośnik co element na pozycji równej szerokości. Linia 25. prawy ukośnik prawy ukośnik prefikso minus sufiksu. Linia 26. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy. Linia 30. return T średnik. Linia 31. zamknij nawias klamrowy. Linia 33. static int szukajWzorcaKMP otwórz nawias okrągły String wzorzec przecinek String tekst zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablicaDopasowan znak równości budowaTablicyKMP otwórz nawias okrągły wzorzec zamknij nawias okrągły średnik. Linia 36. int b znak równości 0 średnik. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tekst kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. while otwórz nawias okrągły b zamknij nawias ostrokątny minus 1 ampersant ampersant wzorzec kropka charAt otwórz nawias okrągły b zamknij nawias okrągły wykrzyknik znak równości tekst kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. b znak równości tablicaDopasowan otwórz nawias kwadratowy b zamknij nawias kwadratowy średnik. Linia 40. zamknij nawias klamrowy. Linia 41. plus plus b średnik. Linia 43. if otwórz nawias okrągły b znak równości znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. return i minus wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły plus 1 średnik. Linia 45. zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy. Linia 47. return minus 1 średnik. Linia 48. zamknij nawias klamrowy. Linia 50. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. String otwórz nawias kwadratowy zamknij nawias kwadratowy slowa znak równości otwórz nawias klamrowy. Linia 52. cudzysłów algorytm cudzysłów przecinek. Linia 53. cudzysłów metoda cudzysłów przecinek. Linia 54. cudzysłów mama cudzysłów przecinek. Linia 55. cudzysłów kajak cudzysłów przecinek. Linia 56. cudzysłów joanna cudzysłów. Linia 57. zamknij nawias klamrowy średnik. Linia 59. 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 61. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny slowa kropka length średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. System kropka out kropka println otwórz nawias okrągły szukajWzorcaKMP otwórz nawias okrągły slowa otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek tekst zamknij nawias okrągły zamknij nawias ostrokątny znak równości 0 znak zapytania cudzysłów TAK cudzysłów dwukropek cudzysłów NIE cudzysłów zamknij nawias okrągły średnik. Linia 63. zamknij nawias klamrowy. Linia 64. zamknij nawias klamrowy. Linia 65. zamknij nawias klamrowy.

public class Main {
    static int[] budowaTablicyKMP(String wzorzec) {
        int rozmiarT = wzorzec.length() + 1;
        int[] T = new int[rozmiarT];
        int poz = -1;
        T[0] = -1;

        // dla każdego kolejnego prefiksu wzorca
        for (int i = 1; i < rozmiarT; ++i) {
            // dopóki możesz znaleźć dłuższy prefikso-sufiks
            while(poz > -1 && wzorzec.charAt(poz) != wzorzec.charAt(i - 1)) {
                poz = T[poz];
            }
            ++poz;

            // jeżeli element występujący po znalezionym
            // prefikso-sufiksie jest taki sam jak po prefiksie
            if (i == rozmiarT - 1 || wzorzec.charAt(i) != wzorzec.charAt(poz)) {
                // zapisz szerokość znalezionego prefikso-sufiksu
                T[i] = poz;
            }
            else {
                // kolejny element tablicy będzie tym samym,
                // co element na pozycji równej szerokości
                // prefikso-sufiksu
                T[i] = T[poz];
            }
        }

        return T;
    }

    static int szukajWzorcaKMP(String wzorzec, String tekst) {
        int[] tablicaDopasowan = budowaTablicyKMP(wzorzec);

        int b = 0;
        for (int i = 0; i < tekst.length(); ++i) {
            while (b > -1 && wzorzec.charAt(b) != tekst.charAt(i)) {
                b = tablicaDopasowan[b];
            }
            ++b;

            if (b == wzorzec.length()) {
                return i - wzorzec.length() + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] slowa = {
            "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.";

        for (int i = 0; i < slowa.length; ++i) {
            System.out.println(szukajWzorcaKMP(slowa[i], tekst) >= 0 ? "TAK" : "NIE");
        }
    }
}

Ćwicz i zwyciężaj

I_P_W14_M16 Algorytm Knutha‑Morrisa‑Pratta