infalo

Filmy

Psie sprawki

Programowanie algorytmu wyszukiwania wzorca w tekście metodą naiwną

—

by

karrolinna
in

Ten materiał jest kursem dla uczniów klasy trzeciej liceum (poziom podstawowy). Pokazuje krok po kroku, jak zaprogramować w Pythonie naiwny algorytm wyszukiwania wzorca w tekście, czyli sposób na znalezienie fragmentu tekstu (wzorca) w dłuższym tekście.

Zakładamy, że kiedyś już programowałeś(aś) w Pythonie, ale możesz nie pamiętać wszystkich szczegółów. Dlatego po drodze przypominamy najważniejsze rzeczy: łańcuchy znaków, pętle, funkcje.

1. Co to znaczy „wyszukać wzorzec w tekście”?

Mamy:

  • tekst – dłuższy napis, np. "ala ma kota"
  • wzorzec – krótszy napis, którego szukamy, np. "ma"

Chcemy odpowiedzieć na pytania:

  • Czy wzorzec występuje w tekście?
  • Jeśli tak, to na jakiej pozycji (indeksie) się zaczyna?
  • Być może chcemy znaleźć wszystkie wystąpienia wzorca w tekście.

Przykład:

tekst   = "ala ma kota"
wzorzec = "ma"

Wzorzec "ma" zaczyna się na pozycji 4 (licząc od 0):
indeksy:  0123456789 10
tekst:    a l a   m a   k o  t  a
           0 1 2 3 4 5 6 7 8 9 10

2. Krótkie przypomnienie Pythona

2.1. Łańcuchy znaków (string)

Łańcuch znaków w Pythonie zapisujemy w cudzysłowach:

tekst = "ala ma kota"
wzorzec = "ma"

Indeksy (pozycje znaków) zaczynają się od 0:

tekst[0]  # 'a'
tekst[1]  # 'l'
tekst[2]  # 'a'
tekst[3]  # ' '
tekst[4]  # 'm'

2.2. Funkcja len()

Funkcja len() zwraca długość łańcucha (ile ma znaków):

len("ala")        # 3
len("ala ma kota")# 11

2.3. Pętla for – powtarzanie czynności

Pętla for pozwala wykonać kod wiele razy. Na przykład:

for i in range(5):
    print(i)

Wypisze:

0
1
2
3
4

Funkcja range(n) tworzy liczby od 0 do n-1.

2.4. Funkcja – jak zrobić „własne polecenie”

Funkcja to fragment kodu, który możemy wywołać po nazwie:

def przywitaj():
    print("Cześć!")

przywitaj()  # wywołanie funkcji

Funkcja może przyjmować argumenty i zwracać wynik:

def dodaj(a, b):
    wynik = a + b
    return wynik

x = dodaj(2, 3)
print(x)  # x = 5

3. Pomysł na naiwny algorytm wyszukiwania

„Naiwny” znaczy tutaj: bez sprytnych skrótów, po prostu sprawdzamy wszystko po kolei.

Idea:

  1. Bierzemy kolejne miejsca w tekście jako możliwy początek wzorca.
  2. Dla każdego takiego miejsca porównujemy znak po znaku wzorzec z fragmentem tekstu.
  3. Jeśli wszystkie znaki się zgadzają – znaleźliśmy wzorzec.
  4. Jeśli nie – przesuwamy się o jedno miejsce w tekście i próbujemy dalej.

Przykład: tekst "ala ma kota", wzorzec "ma".

  • Poz. 0: porównujemy "al" z "ma" → nie pasuje
  • Poz. 1: porównujemy "la" z "ma" → nie pasuje
  • Poz. 2: porównujemy "a " z "ma" → nie pasuje
  • Poz. 3: porównujemy " m" z "ma" → nie pasuje
  • Poz. 4: porównujemy "ma" z "ma" → pasuje 🎉

4. Jak daleko możemy się przesuwać?

Załóżmy, że:

  • długość tekstu to n = len(tekst),
  • długość wzorca to m = len(wzorzec).

Jeśli wzorzec zaczyna się na pozycji i, to ostatni znak wzorca ma indeks i + m - 1. To musi być w zakresie tekstu, więc:

i + m - 1 < n

Czyli:

i <= n - m

Zatem jako początek wzorca możemy brać indeksy od 0 do n - m (włącznie).

5. Naiwne wyszukiwanie – implementacja krok po kroku

5.1. Wersja zwracająca pierwszy indeks

Napiszemy funkcję, która:

  • zwraca indeks pierwszego wystąpienia wzorca w tekście,
  • albo -1, jeśli wzorzec się nie pojawia.
def znajdz_wzorzec(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)

    # Przypadek szczególny: pusty wzorzec
    if m == 0:
        return 0  # umówmy się, że zwracamy 0

    # i to potencjalny początek dopasowania
    for i in range(n - m + 1):
        # Zakładamy, że na pozycji i jest dopasowanie
        pasuje = True

        # Sprawdzamy każdy znak wzorca
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break  # wyjście z pętli po wzorcu

        # jeśli po sprawdzeniu wszystkich znaków nadal pasuje, znaleźliśmy
        if pasuje:
            return i

    # jeśli nigdzie nie pasowało
    return -1

Przykłady użycia:

print(znajdz_wzorzec("ala ma kota", "ma"))   # 4
print(znajdz_wzorzec("bbbbbb", "bb"))        # 0
print(znajdz_wzorzec("abcdef", "gh"))        # -1

5.2. Wersja znajdująca wszystkie wystąpienia

Często chcemy znaleźć wszystkie miejsca, gdzie pojawia się wzorzec. Wtedy zamiast zwracać jeden indeks, tworzymy listę indeksów.

def znajdz_wszystkie(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)
    pozycje = []

    if m == 0:
        # umówmy się, że pusty wzorzec nie ma sensu – zwracamy pustą listę
        return pozycje

    for i in range(n - m + 1):
        pasuje = True
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break
        if pasuje:
            pozycje.append(i)

    return pozycje

Przykłady:

print(znajdz_wszystkie("aaaaa", "aa"))  # [0, 1, 2, 3]
print(znajdz_wszystkie("ala ma kota", "a"))  # [0, 2, 5, 9, 11] (dla "ala ma kota a")

6. Analiza działania krok po kroku – przykład

Rozważmy:

tekst = "banana"
wzorzec = "ana"

Długości:

  • n = len("banana") = 6
  • m = len("ana") = 3
  • i będzie przyjmować wartości od 0 do 6 - 3 = 3, czyli 0, 1, 2, 3

Sprawdzamy:

  1. i = 0: porównujemy "ban" z "ana" → nie pasuje
  2. i = 1: porównujemy "ana" z "ana" → pasuje ✔
  3. i = 2: porównujemy "nan" z "ana" → nie pasuje
  4. i = 3: porównujemy "ana" z "ana" → pasuje ✔

Zatem wszystkie wystąpienia wzorca są na pozycjach [1, 3].

7. Skażoność czasowa – ile to trwa?

W najgorszym przypadku – gdy wzorzec prawie pasuje w wielu miejscach, ale ostatecznie nie – musimy:

  • sprawdzić około n możliwych pozycji,
  • na każdej pozycji porównać do m znaków.

Czyli liczba porównań jest rzędu n · m. Dla liceum wystarczy zapamiętać: algorytm naiwny jest dość wolny, ale prosty do zrozumienia i zaprogramowania.

8. Zadania z rozwiązaniami

Zadanie 1. Pierwsze wystąpienie wzorca

Napisz funkcję pierwsze_wystapienie(tekst, wzorzec), która:

  • zwraca indeks pierwszego wystąpienia wzorca w tekście,
  • zwraca -1, jeśli wzorzec nie występuje.

Nie używaj wbudowanej metody tekst.find() – zaimplementuj algorytm naiwny.

Rozwiązanie

def pierwsze_wystapienie(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)

    if m == 0:
        return 0  # pusty wzorzec

    for i in range(n - m + 1):
        pasuje = True
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break
        if pasuje:
            return i

    return -1

# Przykłady testowe:
print(pierwsze_wystapienie("ala ma kota", "ma"))   # 4
print(pierwsze_wystapienie("testtest", "stt"))     # -1
print(pierwsze_wystapienie("banana", "ana"))       # 1

Zadanie 2. Czy wzorzec występuje w tekście?

Napisz funkcję czy_wystepuje(tekst, wzorzec), która:

  • zwraca True, jeśli wzorzec występuje w tekście,
  • zwraca False w przeciwnym razie.

Rozwiązanie

Wykorzystamy funkcję z poprzedniego zadania albo napiszemy podobną:

def czy_wystepuje(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)

    if m == 0:
        return True  # pusty wzorzec – załóżmy, że „występuje”

    for i in range(n - m + 1):
        pasuje = True
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break
        if pasuje:
            return True

    return False

# Przykłady:
print(czy_wystepuje("ala ma kota", "ma"))   # True
print(czy_wystepuje("abcdef", "gh"))        # False

Zadanie 3. Liczba wystąpień wzorca

Napisz funkcję policz_wystapienia(tekst, wzorzec), która liczy, ile razy wzorzec występuje w tekście (mogą się nakładać, np. w „aaaa” wzorzec „aa” występuje 3 razy).

Rozwiązanie

def policz_wystapienia(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)
    licznik = 0

    if m == 0:
        return 0  # pustego wzorca nie liczymy

    for i in range(n - m + 1):
        pasuje = True
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break
        if pasuje:
            licznik += 1

    return licznik

# Przykłady:
print(policz_wystapienia("aaaa", "aa"))      # 3 (pozycje: 0,1,2)
print(policz_wystapienia("banana", "ana"))   # 2 (pozycje: 1,3)
print(policz_wystapienia("abc", "d"))        # 0

Wyjaśnienie:

  • Przechodzimy po wszystkich możliwych pozycjach początku wzorca.
  • Jeśli na danej pozycji wszystkie znaki wzorca się zgadzają, zwiększamy licznik.
  • Na końcu zwracamy licznik.

Zadanie 4. Znajdź wszystkie pozycje wystąpienia wzorca

Napisz funkcję wszystkie_pozycje(tekst, wzorzec), która zwróci listę indeksów, na których zaczyna się wzorzec w tekście. Jeśli wzorca nie ma – zwróć pustą listę.

Rozwiązanie

def wszystkie_pozycje(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)
    pozycje = []

    if m == 0:
        return pozycje  # pusty wzorzec – nic nie zwracamy

    for i in range(n - m + 1):
        pasuje = True
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break
        if pasuje:
            pozycje.append(i)

    return pozycje

# Przykłady:
print(wszystkie_pozycje("banana", "ana"))   # [1, 3]
print(wszystkie_pozycje("aaaaa", "aa"))     # [0, 1, 2, 3]
print(wszystkie_pozycje("abc", "d"))        # []

To jest ten sam algorytm, co wcześniej, tylko zamiast licznika używamy listy, do której dopisujemy pozycje, gdy znajdziemy dopasowanie.

Zadanie 5. Napisz prosty program do wyszukiwania wzorca

Napisz program, który:

  1. wczyta z klawiatury tekst,
  2. wczyta z klawiatury wzorzec,
  3. wykorzysta naiwny algorytm, aby znaleźć wszystkie wystąpienia wzorca,
  4. wypisze informację: ile wystąpień i na jakich pozycjach.

Rozwiązanie

def wszystkie_pozycje(tekst, wzorzec):
    n = len(tekst)
    m = len(wzorzec)
    pozycje = []

    if m == 0:
        return pozycje

    for i in range(n - m + 1):
        pasuje = True
        for j in range(m):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break
        if pasuje:
            pozycje.append(i)

    return pozycje

# Główna część programu
tekst = input("Podaj tekst: ")
wzorzec = input("Podaj wzorzec: ")

pozycje = wszystkie_pozycje(tekst, wzorzec)

if len(pozycje) == 0:
    print("Wzorzec nie występuje w tekście.")
else:
    print("Wzorzec występuje", len(pozycje), "razy.")
    print("Pozycje początkowe:", pozycje)

Wyjaśnienie:

  • Najpierw definiujemy funkcję wszystkie_pozycje (znasz ją z poprzedniego zadania).
  • Wczytujemy dane od użytkownika funkcją input().
  • Wywołujemy funkcję i zapisujemy wynik w zmiennej pozycje.
  • Jeśli lista jest pusta – wypisujemy, że wzorzec nie występuje.
  • W przeciwnym razie wypisujemy liczbę wystąpień i listę pozycji.

9. Podsumowanie – co warto zapamiętać

  • Naiwny algorytm wyszukiwania wzorca:
    • próbuje dopasować wzorzec w każdym możliwym miejscu tekstu,
    • porównuje znak po znaku wzorzec z fragmentem tekstu.
  • Potrzebne elementy Pythona:
    • łańcuchy znaków (stringi) i indeksowanie,
    • funkcja len(),
    • pętle for,
    • instrukcja if i break,
    • funkcje z def i return.
  • W najgorszym przypadku algorytm wykonuje około n · m porównań (n – długość tekstu, m – długość wzorca).

Opanowanie tego algorytmu to dobry punkt wyjścia do poznawania bardziej zaawansowanych metod wyszukiwania, ale przede wszystkim – świetne ćwiczenie logicznego myślenia i programowania w Pythonie.