KMP Önek İşlevi
O(n + m) içinde bir desen bulun.
KMP Önek İşlevi, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
Örüntü Eşleme Problemi
Büyük bir metnin içinde küçük bir örüntünün nerede göründüğünü bulmak istiyorsunuz. Naif denemeler yavaştır; bu nedenle yarışmalarda daha akıllı bir tarama gerekir. 🔍
Naif Arama Neden Zorlayıcıdır
Örüntüyü her konumda karşılaştırmak O(n*m) zaman alabilir. Büyük girdilerde bu, fark ettirmeden süre sınırınızı aşar.
Önek İşleviyle Tanışın
Önek işlevi, her konumda aynı zamanda sonek olan en uzun öz öneki ölçer. KMP'nin temelini oluşturur.
Öz Önek ve Sonek
Öz bir önek veya sonek, dizenin tamamını kendisi olarak dışarıda bırakır. ababa için en uzun eşleşen çiftin uzunluğu 3'tür: aba.
pi[i] Ne Saklar
Değerleri pi adlı bir dizide saklarız. Burada pi[i], i indisinde biten parçanın en uzun önek-sonek uzunluğudur.
pi'yi Tek Geçişte Oluşturma
pi dizisini soldan sağa oluşturur, baştan yeniden kontrol etmek yerine önceki değerleri yeniden kullanırsınız. Bütün numara bu yeniden kullanımdan ibarettir.
def prefix_function(s):
pi = [0] * len(s)
return piGeri Dönüş Döngüsü
Karakterler uyuşmadığında sıfıra dönmek yerine pi[k-1] değerine geri dönersiniz. Böylece yapılan işi tekrarlamazsınız.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Eşleşmeyi Uzatma
Geçerli karakterler eşleşiyorsa, uzunluğu bir artırıp kaydedersiniz. Sıfır uzunluğundaki uyuşmazlıklar sıfır olarak kalır.
if s[i] == s[k]:
k += 1
pi[i] = kBu Yöntemle Arama
Bir metinde örüntü aramak için ikisini pattern + sep + text biçiminde birleştirin. Örüntü uzunluğuna eşit herhangi bir pi değeri, tam bir eşleşmeyi gösterir.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Ayraç Neden Önemlidir
Ayraç, iki dizenin hiçbirinde bulunmayan bir simgedir. Eşleşmelerin birleştirme noktasını aşarak yanlış sonuçlar vermesini önler.
Doğrusal Zamanın Kazancı
Hem oluşturma hem de arama O(n + m) sürede çalışır. Her karakter bir kez işlendiği için KMP, çok büyük yarışma girdilerine ölçeklenebilir.
Hızlı Kontrol
Önek işlevinin neyi kaydettiğini ne kadar iyi kavradığınızı sınayın.
Özet: KMP Kısaca
Önek işlevini öğrendiniz: pi dizisini bir kez oluşturun, uyuşmazlıklarda geri dönün ve doğrusal zamanda arayın. Kısaca KMP budur. 🎯
Sıkça Sorulan Sorular
“KMP Önek İşlevi” dersi ücretsiz mi?
Evet — “KMP Önek İşlevi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“KMP Önek İşlevi” dersinde ne öğreneceğim?
O(n + m) içinde bir desen bulun. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“KMP Önek İşlevi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.