Düz Desen Arama

#Nasıl çalışır?

Desen arama (string matching), bir metin içinde bir desenin geçtiği tüm konumları bulma problemidir. En basit yöntem deseni metnin her olası başlangıç konumuna yerleştirip harf harf karşılaştırmaktır.

Her konumda karşılaştırma desenin başından başlar ve ilk uyuşmazlıkta durur; desen bir sağa kaydırılır ve her şey baştan yapılır. Tüm harfler tutarsa bir eşleşme bulunmuştur.

Bu yöntem çoğu gerçek metinde hızlıdır, çünkü uyuşmazlıklar genellikle ilk birkaç harfte çıkar. Ama AAAA…AB gibi tekrarlı metinlerde aynı harfler defalarca karşılaştırılır ve maliyet O(n · m)'ye çıkar.

#Kendin dene

#Adım adım

1. 01Deseni metnin ilk konumuna hizala.
2. 02Harfleri baştan karşılaştır; ilk uyuşmazlıkta dur.
3. 03Tüm harfler tuttuysa eşleşmeyi kaydet.
4. 04Deseni bir sağa kaydır ve son konuma kadar tekrarla.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def search(text: str, pattern: str) -> list:
    """Every 0-based position where pattern starts in text."""
    n, m = len(text), len(pattern)
    found = []
    for s in range(n - m + 1):  # every shift of the pattern
        j = 0
        while j < m and text[s + j] == pattern[j]:
            j += 1
        if j == m:
            found.append(s)
    return found


print(" ".join(map(str, search("AABAACAADAABAABA", "AABA"))))

#Karmaşıklık

n metin, m desen uzunluğudur. Desen n − m + 1 konumda denenir ve her konumda en fazla m karşılaştırma yapılır. Ön hazırlık gerektirmediği için kısa desenlerde ve tek seferlik aramalarda hâlâ iyi bir seçimdir.

#Ne zaman kullanılır?

Kısa desenler ve kısa metinler, tek seferlik aramalar ve basitliğin önemli olduğu yerler. Birçok standart kütüphanenin indexOf / find fonksiyonu kısa girdiler için bu yöntemin optimize edilmiş bir hâlini kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• KMP Algoritması
• Rabin-Karp Algoritması