KMP Algoritması

#Nasıl çalışır?

Knuth-Morris-Pratt (KMP) algoritması, düz aramanın tekrar tekrar aynı harfleri karşılaştırma sorununu çözer. Uyuşmazlık olduğunda metinde asla geri dönmez; zaten tutan harflerden yararlanarak deseni ileri kaydırır.

Bunun için önce desenden bir önek tablosu (lps, "longest proper prefix which is also suffix") hesaplanır: lps[j], desenin ilk j + 1 harfinde hem önek hem sonek olan en uzun parçanın uzunluğudur. ABABCABAB için tablo 0 0 1 2 0 1 2 3 4'tür.

j harf tuttuktan sonra bir uyuşmazlık çıkarsa, tutan kısmın son lps[j − 1] harfi desenin başıyla zaten aynıdır. Desen buna göre kaydırılır ve karşılaştırma oradan sürer. Böylece metindeki her harf en fazla iki kez karşılaştırılır.

#Kendin dene

#Adım adım

1. 01Desenin önek tablosunu (lps) hesapla.
2. 02Metin ve desen işaretçileriyle ilerle; harfler eşitse ikisini de ilerlet.
3. 03Desen tamamen tuttuysa eşleşmeyi kaydet ve j = lps[j − 1] yap.
4. 04Uyuşmazlıkta j > 0 ise j = lps[j − 1]; j = 0 ise metinde bir harf ilerle.

#Örnek kod

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

def prefix_table(pattern: str) -> list:
    """lps[i] = longest proper prefix of pattern[:i + 1] that is also its suffix."""
    lps = [0] * len(pattern)
    length, i = 0, 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]
        else:
            i += 1
    return lps


def kmp_search(text: str, pattern: str) -> list:
    lps = prefix_table(pattern)
    found, i, j = [], 0, 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                found.append(i - j)
                j = lps[j - 1]
        elif j > 0:
            j = lps[j - 1]  # slide the pattern; i never moves back
        else:
            i += 1
    return found


print(" ".join(map(str, prefix_table("ABABCABAB"))))
print(" ".join(map(str, kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))))

#Karmaşıklık

Metin işaretçisi hiç geri gitmez ve her uyuşmazlık deseni en az bir konum kaydırır; bu yüzden toplam karşılaştırma sayısı 2n'yi geçmez. Önek tablosu da aynı fikirle O(m)'de kurulur.

#Ne zaman kullanılır?

Uzun metinlerde ve tekrarlı içerikte garantili doğrusal arama: DNA dizileri, log dosyaları, akış (stream) halinde gelen veride desen arama. Önek tablosu fikri ayrıca bir dizgideki en kısa tekrar eden birimi bulmak gibi problemlerde de kullanılır.

#Alıştırma

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