Analiza programu krok po kroku - I_P_W14_M15_C++ Algorytmy tekstowe w języku C++

RmtGf1Gvh45gA

Program realizujący algorytm wyszukiwania wzorca w tekście metodą naiwną

Specyfikacja algorytmu:

Znaleźć wszystkie pozycje w tekście, na których występuje zadany wzorzec (ciąg znaków).

Dane wejściowe:

tekst – ciąg znaków, w którym szukamy wzorca (np. sekwencja DNA, zdanie, kod).
wzorzec – ciąg znaków, który chcemy znaleźć w tekście.

Dane wyjściowe:

Lista pozycji (indeksów), na których wzorzec występuje w tekście.
Jeśli wzorzec nie występuje – informacja o jego braku.

Złożoność obliczeniowa:

Czasowa: O(n × m), gdzie:
- n – długość tekstu,
- m – długość wzorca.
Pamięciowa: O(1) – nie wymaga dodatkowej pamięci poza zmiennymi pomocniczymi.

Oto szczegółowe omówienie programu w C++, który realizuje naiwne wyszukiwanie wzorca w tekście. Przeanalizujmy go linijka po linijce, aby zrozumieć każdy element.

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 3. using namespace std średnik. Linia 5. void naiwnyWyszukiwacz otwórz nawias okrągły string tekst przecinek string wzorzec zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int n znak równości tekst kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 7. int m znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 9. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości n minus m średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. int j średnik. Linia 11. for otwórz nawias okrągły j znak równości 0 średnik j otwórz nawias ostrokątny m średnik plus plus j zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. if otwórz nawias okrągły tekst otwórz nawias kwadratowy i plus j zamknij nawias kwadratowy wykrzyknik znak równości wzorzec otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły. Linia 13. break średnik. Linia 14. zamknij nawias klamrowy. Linia 15. if otwórz nawias okrągły j znak równości znak równości m zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wzorzec znaleziony na pozycji cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 17. zamknij nawias klamrowy. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. string tekst znak równości cudzysłów Ala ma kota i kot ma Ale cudzysłów średnik. Linia 23. string wzorzec znak równości cudzysłów ma cudzysłów średnik. Linia 25. naiwnyWyszukiwacz otwórz nawias okrągły tekst przecinek wzorzec zamknij nawias okrągły średnik. Linia 27. return 0 średnik. Linia 28. zamknij nawias klamrowy.

#include <iostream>
#include <string>
using namespace std;

void naiwnyWyszukiwacz(string tekst, string wzorzec) {
    int n = tekst.length();
    int m = wzorzec.length();

    for (int i = 0; i <= n - m; ++i) {
        int j;
        for (j = 0; j < m; ++j) {
            if (tekst[i + j] != wzorzec[j])
                break;
        }
        if (j == m) {
            cout << "Wzorzec znaleziony na pozycji " << i << endl;
        }
    }
}

int main() {
    string tekst = "Ala ma kota i kot ma Ale";
    string wzorzec = "ma";

    naiwnyWyszukiwacz(tekst, wzorzec);

    return 0;
}

1. Nagłówki i przestrzeń nazw

#include <iostream>
#include <string>
using namespace std;

Dodajemy biblioteki potrzebne do pracy z tekstem i wejściem/wyjściem.

2. Definicja funkcji wyszukującej

void naiwnyWyszukiwacz(string tekst, string wzorzec)

Funkcja przyjmuje dwa argumenty typu string: tekst – to ciąg znaków, w którym szukamy wzorca, wzorzec – to ciąg znaków, który próbujemy znaleźć.

3. Obliczenie długości tekstu i wzorca

int n = tekst.length();
int m = wzorzec.length();

Obliczamy długości tekstu i wzorca, by wiedzieć, ile razy możemy przesunąć wzorzec w tekście.
n – liczba znaków w tekście, m – liczba znaków we wzorcu

4. Główna pętla przeszukująca tekst

    for (int i = 0; i <= n - m; ++i) {
        int j;
        for (j = 0; j < m; ++j) {
            if (tekst[i + j] != wzorzec[j])
                break;
        }
        if (j == m) {
            cout << "Wzorzec znaleziony na pozycji " << i << endl;
        }
    }

for (int i = 0; i <= n - m; i++) Przesuwamy wzorzec po tekście – od początku do miejsca, gdzie jeszcze może się zmieścić.

for (j = 0; j < m; j++) Porównujemy znak po znaku wzorzec z fragmentem tekstu zaczynającym się od pozycji i.

5. Porównywanie znaków wzorca z tekstem

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

Jeśli którykolwiek znak się nie zgadza – przerywamy porównywanie.

if (j == m)
Jeśli udało się porównać wszystkie znaki wzorca – mamy trafienie!

cout << "Wzorzec znaleziony na pozycji: " << i << endl; Wyświetlamy informację o znalezieniu wzorca.

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 3. using namespace std średnik. Linia 5. prawy ukośnik prawy ukośnik Funkcja wyszukująca wzorzec w tekście metodą naiwną. Linia 6. void naiwnyWyszukiwacz otwórz nawias okrągły string tekst przecinek string wzorzec zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int n znak równości tekst kropka length otwórz nawias okrągły zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik Długość tekstu. Linia 8. int m znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik Długość wzorca. Linia 10. prawy ukośnik prawy ukośnik Przesuwamy wzorzec przez cały tekst. Linia 11. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości n minus m średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. int j średnik. Linia 13. prawy ukośnik prawy ukośnik Porównujemy znaki wzorca z fragmentem tekstu. Linia 14. for otwórz nawias okrągły j znak równości 0 średnik j otwórz nawias ostrokątny m średnik plus plus j zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły tekst otwórz nawias kwadratowy i plus j zamknij nawias kwadratowy wykrzyknik znak równości wzorzec otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły. Linia 16. break średnik. Linia 17. zamknij nawias klamrowy. Linia 18. prawy ukośnik prawy ukośnik Jeśli wszystkie znaki pasują przecinek wypisz pozycję. Linia 19. if otwórz nawias okrągły j znak równości znak równości m zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wzorzec znaleziony na pozycji cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy.

#include <iostream>
#include <string>
using namespace std;

// Funkcja wyszukująca wzorzec w tekście metodą naiwną
void naiwnyWyszukiwacz(string tekst, string wzorzec) {
    int n = tekst.length();     // Długość tekstu
    int m = wzorzec.length();   // Długość wzorca

    // Przesuwamy wzorzec przez cały tekst
    for (int i = 0; i <= n - m; ++i) {
        int j;
        // Porównujemy znaki wzorca z fragmentem tekstu
        for (j = 0; j < m; ++j) {
            if (tekst[i + j] != wzorzec[j])
                break;
        }
        // Jeśli wszystkie znaki pasują, wypisz pozycję
        if (j == m) {
            cout << "Wzorzec znaleziony na pozycji " << i << endl;
        }
    }
}

int main() {
    string tekst = "Ala ma kota i kot ma Ale";
    string wzorzec = "ma";

    naiwnyWyszukiwacz(tekst, wzorzec);

    return 0;
}

Wynik działania programu:

Wzorzec znaleziony na pozycji 4
Wzorzec znaleziony na pozycji 18

Wyszukiwanie wzorca w tekście metodą naiwną

Misja: Znajdź mutację genetyczną