--- title: Knuth–Morris–Pratt source: 'https://academia.sh/tr/kurslar/algoritmalar/knuth-morris-pratt' course: Algoritmalar language: tr updated: '2026-08-17T18:07:48+00:00' license: 'CC BY-SA 4.0' --- # Knuth–Morris–Pratt Önek işlevinin tanımı ve doğrusal hesabı, metinde geri dönmeyen arama, amortize maliyet çözümlemesi ve dizgi dönemselliği. Kaba kuvvet aramanın israfı, uyuşmazlıktan önce yapılan eşleşmeleri unutmasıydı. Rabin–Karp bu israfı karma ile azalttı ama örüntünün **yapısını** hiç kullanmadı. Knuth–Morris–Pratt algoritmasının fikri şudur: eşleşen kısım zaten biliniyorsa, örüntünün kendi iç tekrarları kaç konumun güvenle atlanabileceğini söyler. ## Gözlem `ABABCABAB` örüntüsü metinle karşılaştırılırken ilk dört karakterin (`ABAB`) eşleştiği, beşincinin uyuşmadığı düşünülsün. Metnin o bölümünde `ABAB` olduğu **kesin olarak bilinir**. Kaba kuvvet bir konum kayar ve metnin `BAB…` bölümünü baştan sınar. Oysa `ABAB`'ın `AB` öneki, aynı zamanda `AB` sonekidir; dolayısıyla iki konum kayarak örüntünün ilk iki karakterini yeniden sınamadan devam edilebilir. Ara konumlar denenmeye değmez, çünkü oradaki karakterlerin ne olduğu zaten biliniyor. Genel kural: eşleşen önekin **hem öneki hem soneki** olan en uzun parça korunur, gerisi atılır. ## Önek İşlevi **Önek işlevi** $\pi$, örüntünün her öneki için "hem öz önek hem sonek olan en uzun parçanın uzunluğunu" verir. "Öz" burada parçanın tamamın kendisi olamayacağı anlamındadır. ```python def onek_islevi(oruntu: str) -> list[int]: """pi[i]: oruntu[0..i] parçasının en uzun öz önek-sonek uzunluğu.""" pi = [0] * len(oruntu) k = 0 for i in range(1, len(oruntu)): while k > 0 and oruntu[i] != oruntu[k]: k = pi[k - 1] # daha kısa bir aday öneke geri çekil if oruntu[i] == oruntu[k]: k += 1 pi[i] = k return pi print(onek_islevi("ABABCABAB")) # [0, 0, 1, 2, 0, 1, 2, 3, 4] print(onek_islevi("AABAACAABAA")) # [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5] print(onek_islevi("ABCDE")) # [0, 0, 0, 0, 0] ``` Değerler doğrudan okunur: `ABABCABAB` örüntüsünün tamamının en uzun önek-sonek örtüşmesi 4'tür (`ABAB`), dördüncü karakterine kadarki `ABAB` parçasınınki 2'dir (`AB`), hiç tekrar içermeyen `ABCDE` için hepsi sıfırdır. Hesabın kendisi, örüntüyü kendisinde aramaktır: `k` değişkeni o ana kadar eşleşen önek uzunluğunu tutar ve uyuşmazlıkta daha kısa bir adaya geri çekilir. Maliyet $O(m)$'dir — gerekçesi aramadakiyle aynıdır ve bir sonraki bölümde verilir. ## Arama Arama, aynı geri çekilme mantığını metin üzerinde uygular. Metin imleci **hiçbir zaman geri gitmez**; yalnızca örüntü imleci geri çekilir. ```python def kmp(metin: str, oruntu: str) -> tuple[list[int], int]: """(konumlar, karakter karşılaştırma sayısı)""" pi = onek_islevi(oruntu) konumlar: list[int] = [] k = 0 sayac = 0 for i, karakter in enumerate(metin): while k > 0 and karakter != oruntu[k]: sayac += 1 k = pi[k - 1] sayac += 1 if karakter == oruntu[k]: k += 1 if k == len(oruntu): konumlar.append(i - len(oruntu) + 1) k = pi[k - 1] # örtüşen sonraki geçişi kaçırma return konumlar, sayac metin = "ABABDABACDABABCABAB" oruntu = "ABABCABAB" print(kmp(metin, oruntu)) # ([10], 23) print(kmp("ABABAB", "AB")) # ([0, 2, 4], 6) print(kmp("A" * 30 + "B", "A" * 10 + "B")) # ([20], 51) ``` Son satır belirleyicidir: kaba kuvvetin 231 karşılaştırma yaptığı girdide KMP 51 yapar. Karesel davranış tamamen ortadan kalkmıştır. Eşleşme bulunduktan sonra `k = pi[k-1]` ataması, örtüşen geçişlerin kaçırılmamasını sağlar. `ABABAB` içinde `ABAB` arandığında 0 ve 2 konumlarının ikisi de bulunur. ## Maliyet Önişleme $O(m)$, arama $O(n)$, toplam $O(n + m)$ — **en kötü durumda**. Ek alan $O(m)$'dir (önek işlevi tablosu). Gerekçe amortize bir akıl yürütmedir; Karmaşıklık Hesaplama Yöntemi dersindeki toplam maliyet yöntemi burada doğrudan uygulanır. `k` değişkeni her turda en çok bir artar; $n$ tur boyunca toplam artış en çok $n$'dir. İç döngünün her turu `k`'yi en az bir azaltır ve `k` hiç negatif olmaz. Dolayısıyla iç döngü toplam en çok $n$ kez çalışabilir. İç döngü tek tek bakıldığında $O(m)$ görünse de, tüm arama boyunca toplam maliyeti doğrusaldır. | Ölçüt | Kaba kuvvet | Rabin–Karp | KMP | |---|---|---|---| | Önişleme | Yok | $O(m)$ | $O(m)$ | | En kötü arama | $O(nm)$ | $O(nm)$ | $O(n)$ | | Ek alan | $O(1)$ | $O(1)$ | $O(m)$ | | Metinde geri dönüş | Var | Yok | Yok | Son satır pratik bir sonuç doğurur: metin imleci geri gitmediği için algoritma, tamamı bellekte olmayan bir **akış** üzerinde çalışabilir. Karakterler geldikçe işlenir, geri sarma gerekmez. ## Özdevinir Görünümü Önek işlevi, aslında bir **sonlu otomatın (finite automaton)** sıkıştırılmış hâlidir. Durumlar "şu ana kadar örüntünün kaç karakteri eşleşti" bilgisini tutar; her karakter için bir geçiş tanımlanır ve son durum bir eşleşme bildirir. Geçişler önceden hesaplanırsa, arama sırasında geri çekilme döngüsü de ortadan kalkar: her metin karakteri için tam olarak bir tablo okuması yapılır. ```python def otomat(oruntu: str, abece: str) -> list[dict[str, int]]: pi = onek_islevi(oruntu) m = len(oruntu) gecis: list[dict[str, int]] = [{} for _ in range(m + 1)] for durum in range(m + 1): for karakter in abece: if durum < m and karakter == oruntu[durum]: gecis[durum][karakter] = durum + 1 # ilerle elif durum == 0: gecis[durum][karakter] = 0 # başa dön else: gecis[durum][karakter] = gecis[pi[durum - 1]][karakter] return gecis def otomatla_ara(metin: str, oruntu: str, abece: str) -> list[int]: gecis = otomat(oruntu, abece) m, durum = len(oruntu), 0 konumlar: list[int] = [] for i, karakter in enumerate(metin): durum = gecis[durum][karakter] if durum == m: konumlar.append(i - m + 1) return konumlar print(otomatla_ara("ABABDABACDABABCABAB", "ABABCABAB", "ABCD")) # [10] ``` Bedel bellektedir: tablo $O(m\sigma)$ yer kaplar ve abece büyükse bu ciddi bir maliyettir. Önek işlevi ise $O(m)$ yer kaplayıp aynı davranışı amortize olarak üretir. İki yaklaşım arasındaki seçim, abece büyüklüğü ile arama sıklığına bakılarak yapılır. ## Dönemsellik Önek işlevi, arama dışında bir bilgiyi de doğrudan verir: bir dizginin **en küçük dönemini**. Uzunluğu $m$ olan bir dizgi için $p = m - \pi[m-1]$ değeri en küçük dönem uzunluğudur. $m$, $p$'ye tam bölünüyorsa dizgi o parçanın tekrarından oluşur. ```python def en_kucuk_donem(dizgi: str) -> tuple[int, bool]: pi = onek_islevi(dizgi) p = len(dizgi) - pi[-1] return p, len(dizgi) % p == 0 for ornek in ("ABABAB", "ABCABCABC", "ABCD", "AAAA"): print(ornek, en_kucuk_donem(ornek)) # ABABAB (2, True) # ABCABCABC (3, True) # ABCD (4, True) # AAAA (1, True) ``` `ABCD` için dönem uzunluğun kendisidir: tekrar yoktur. Bu hesap, sıkıştırmada ve dizgi denkliği sorularında kullanılır; aynı tablo iki farklı işe yarar. ## Özet - KMP, eşleşen önekin önek–sonek örtüşmesini kullanarak uyuşmazlıkta kaç konumun atlanabileceğini belirler. - Önek işlevi her önek için en uzun öz önek–sonek uzunluğunu verir ve $O(m)$'de hesaplanır. - Aramada metin imleci hiç geri gitmez; yalnızca örüntü imleci geri çekilir. - Toplam maliyet $O(n + m)$'dir; gerekçe, `k` değişkeninin toplam artışını sınırlayan amortize akıl yürütmedir. - Metinde geri dönüş olmaması, algoritmayı akış verisi için uygun kılar. - Aynı tablo, bir dizginin en küçük dönemini de verir. ## Sonraki Adım KMP, örüntüyü baştan sona eşleştirir ve metnin her karakterine en az bir kez bakar. Sonraki ders ters yönden eşleştiren bir yaklaşımı ele alacak: örüntünün **sonundan** başlayan karşılaştırma, uyuşmazlık anında metnin bazı karakterlerine **hiç bakmadan** atlamayı mümkün kılar ve pratikte doğrusalın altında davranış üretir.