Wyszukaj wzorzec w tekście

Program symuluje działanie algorytmy wyszukiwania wzorca w tekście

Algorytm naiwny polega na porównywaniu kolejnych znaków tekstu i wzorca. Zaczynamy od sprawdzenia pierwszego znaku tekstu i pierwszego znaku wzorca: jeśli są zgodne, sprawdzamy zgodność drugiego znaku tekstu i drugiego znaku wzorca, gdy nie są zgodne, sprawdzamy zgodność drugiego znaku tekstu i pierwszego znaku wzorca itd. – aż do znalezienia wzorca.

Zobacz

Przykładowe implementacje w Pythonie

  1. tekst = "matematyka"
  2. wzorzec = "mat"
  3.  
  4. #wersja z podręcznika - funkcja zwracająca pierwsze (od pozycji startowej) wystąpienie wzorca - pozycje 1 litery wzorca
  5. #lub -1 gdy wzorzec nie występuje
  6. def znajdz_tekst(tekst, wzorzec, pozycja_startowa):
  7.   dl1 = len(tekst)
  8.   dl2 = len(wzorzec)
  9.  
  10.   for i in range(pozycja_startowa, dl1-dl2+1):
  11.     for j in range(dl2):
  12.       if tekst[i+j] != wzorzec[j]:
  13.         break
  14.       if j == dl2-1:
  15.         return i
  16.   return -1
  17.  
  18. #moja wersja z funkcją nie zwracającą wartości, tylko wypisującą wystąpienia wzorca
  19. def znajdz_wzorzec(tekst, wzorzec):
  20.   dl1 = len(tekst)
  21.   dl2 = len(wzorzec)
  22.   liczba_wystapien = 0
  23.  
  24.   for i in range(dl1-dl2+1):
  25.     if tekst[i] == wzorzec[0]:
  26.       if tekst[i:i+dl2] == wzorzec:
  27.         print(f"Znaleziono: | {tekst} | {wzorzec} | {i}")
  28.         liczba_wystapien += 1
  29.  
  30.   if liczba_wystapien == 0:
  31.       print(f"Nie znaleziono wzorca: {wzorzec} w tekście {tekst}")
  32.   else:
  33.       print(f"Wzorzec znaleziono: {liczba_wystapien} razy")
  34.  
  35. #metoda z wykorzystaniem find(tekst, start) - metoda zwracająca pierwsze wystąpienie wzorca (od pozycji startowej)
  36. # lub -1 gdy wzorzec nie występuje
  37. # Funkcja zwraca wszystkie wystąpienia wzorca w formie listy na podstawie której można wypisać wystąpienia ich liczbę
  38. def znajdz_wzorzec_find(tekst, wzorzec):
  39.   dl1 = len(tekst)
  40.   dl2 = len(wzorzec)
  41.   wystapienia = []
  42.   poz = 0
  43.   while poz < dl1-dl2+1 and poz != -1:
  44.     poz = tekst.find(wzorzec, poz)
  45.     if poz !=-1: 
  46.       wystapienia.append(poz)
  47.       poz += 1
  48.   return wystapienia
  49.  
  50. ## Przykładowe użycie
  51. print(znajdz_tekst(tekst, wzorzec, 0))
  52. znajdz_wzorzec(tekst, wzorzec)
  53. print(znajdz_wzorzec_find(tekst, wzorzec))