Wyszukiwanie wzorca w tekście w Pythonie

powrót

Algorytm sprawdza, czy w podanym tekście występuje wzorzec, czyli inny tekst.

Przykład

• Tekst: "Ala ma kota"
• Wzorzec: "kota"

W przykładzie powyżej w podanym tekście "Ala ma kota" występuje wzorzec "kota".

Zasada działania algorytmu

Do rozwiązania zadania użyjemy algorytmu naiwnego, który wykonuje się w czasie $$O(n \cdot k),$$gdzie n to długość wzorca, natomiast k to długość tekstu.

Przeanalizujmy przykład dla tekstu bababac, w którym chcemy sprawdzić, czy występuje fraza bac.

Algorytm będzie sprawdzał, czy pierwsza litera w tekście jest taka sama jak pierwsza litera we wzorcu, jeśli jest zgodność, to sprawdzamy zgodność kolejnych liter. Jeśli po drodze napotkamy niezgodność, to zabawę zaczynamy od nowa porównując odpowiednie litery ze wzroca ze znakami z tekstu począwszy od kolejnej litery:

Warto zwrócić uwagę, że od pewnego momentu, a dokładnie od $$len\left(tekst\right) - len\left(wzorzec\right) + 1$$ litery w tekście, nie ma sensu już sprawdzać, ponieważ pozostała liczba znaków jest mniejsza niż długość wzorca.

Zadanie

Sprawdź, czy podany wzorzec występuje w tekście. Zadbaj o interakcję programu z użytkownikiem.

#*****************www.algorytm.edu.pl****************
def sprawdz(wzorzec, tekst):
    # algorytm sprawdza, czy występuje wzorzec w czasie O(n*k),
    # gdzie "n" to długość wzorca a "k" to długość tekstu
    n = len(wzorzec); k = len(tekst)
    for i in range(k - n + 1):  # od k-n+1 znaku nie ma sensu sprawdzać,
                                # ponieważ pozostała liczba znaków jest mniejsza niż długość wzorca
        for j in range(n): # tyle znaków musi się zgadzać
            if tekst[i + j] != wzorzec[j]: # jeśli nie ma zgodności
                break                      # to dalej nie sprawdzamy
            elif j == n - 1: # jeśli wszystkie znaki się zgadzają
                return True # to zwraca
    return False

tekst = input("Podaj tekst: ")
wzorzec = input("Podaj wzorzec: ")
if sprawdz(wzorzec, tekst):
    print(f"wzorzec \"{wzorzec}\" występuje w tekście \"{tekst}\"")
else:
    print(f"wzorzec \"{wzorzec}\" nie występuje w tekście \"{tekst}\"")