23

Wyszukiwanie wzorca w tekście

Materiały tej lekcji są na razie tylko do czytania na stronie. Kod przepisz albo skopiuj do swojego edytora.

Czego się nauczysz

Napisy to w Pythonie ciągi znaków, po których można chodzić pętlą jak po liczbach. Na tej lekcji policzysz litery w kodzie DNA i napiszesz algorytm, który znajduje wszystkie miejsca, gdzie w tekście występuje szukany wzorzec.

Po tej lekcji:

Napis to ciąg znaków

s = "CAATAAAAA"
print(len(s), s[0], s[-1])   # 9 C A
print("TAA" in s)            # True
print("GG" in s)             # False

Kod DNA zapisuje się literami A, C, G, T. Biolodzy szukają w nim wzorców – to dokładnie problem wyszukiwania w tekście.

Zliczanie liter – dwa sposoby

Sposób 1: pętla i liczniki – przeglądasz napis znak po znaku i zwiększasz licznik odpowiedniej litery.

def ile_liter(s):
    ile_a = ile_c = ile_g = ile_t = 0
    for znak in s:
        if znak == "A":
            ile_a = ile_a + 1
        elif znak == "C":
            ile_c = ile_c + 1
        elif znak == "G":
            ile_g = ile_g + 1
        else:
            ile_t = ile_t + 1
    return [ile_a, ile_c, ile_g, ile_t]

Sposób 2: metoda count – s.count("A") zwraca liczbę wystąpień. Wynik ten sam, kod krótszy. Dla "TCTAAAGATATCGGG" oba sposoby dają [5, 2, 4, 4].

Algorytm naiwny

Przesuwasz wzorzec po tekście: dla każdej pozycji i porównujesz fragment tekstu o długości wzorca z wzorcem. Gdy są równe – zapisujesz pozycję. Wycinek s[i:i+m] zwraca m znaków od pozycji i.

def wystapienia(tekst, wzorzec):
    pozycje = []
    m = len(wzorzec)
    for i in range(len(tekst) - m + 1):
        if tekst[i:i + m] == wzorzec:
            pozycje.append(i)
    return pozycje

wystapienia("ABRAKADABRA", "ABRA")   # [0, 7]

Ostatnia sensowna pozycja to len(tekst) - len(wzorzec).

Nakładające się wystąpienia

wystapienia("AAAA", "AA") zwraca [0, 1, 2] – trzy wystąpienia, które na siebie zachodzą. Metoda "AAAA".count("AA") zwraca 2, bo liczy tylko rozłączne wystąpienia.

Metoda find: "ABRAKADABRA".find("KAD") zwraca 4 – pozycję pierwszego wystąpienia; gdy wzorca brak, zwraca −1.

Indeksy zaczynają się od 0, a wielkość liter ma znaczenie: „a” to nie „A”. range(len(tekst) - m + 1) – bez + 1 pominiesz wzorzec na samym końcu tekstu.

Spróbuj sam

Uruchom kod z lekcji na stronie. Zmień tekst i wzorzec w wywołaniu wystapienia, np. poszukaj „TA” w napisie z DNA. Sprawdź, co zwróci funkcja, gdy wzorca w tekście nie ma.

Na karcie pracy do tej lekcji: zadania sprawdzające 1–3 razem na lekcji i zadania domowe 1–5 samodzielnie.

Sprawdź się

Na następnej lekcji: przetwarzanie napisów – wycinki, palindromy, szyfr przestawieniowy.

Notatki

PDF
Zadania utrwalające Karta pracy do tej lekcji: zadania sprawdzające i domowe do samodzielnego zrobienia w swoim edytorze · 3 strony.
Zadania utrwalające – Wyszukiwanie wzorca w tekście
Strona 1 z 3 Strona 2 z 3 Strona 3 z 3

Prezentacja

Slajd 1 z 7
1 / 7

Kod

Otwórz kod, zmieniaj go i uruchamiaj na stronie – np. usuń # z linii oznaczonej jako błąd i zobacz, co się stanie. „Przywróć” wraca do wersji z lekcji.

PY
L23_wzorzec.py Kod z lekcji – otwórz, zmieniaj i uruchamiaj; wynik zobaczysz obok kodu.
L23_wzorzec.py
Wynik programu
Kliknij „Uruchom”, żeby zobaczyć tutaj wynik programu.