Desen Araması için Z-İşlevi
Dize boyunca önekleri eşleştirin.
Desen Araması için Z-İşlevi, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Bir başka eşleştirme aracı
Z işlevi, desen aramak için KMP'ye temiz bir alternatiftir. Birçok kişi bunun mantığını kavramayı daha kolay bulur. ✨
z[i] ne anlama gelir
Her dizin için z[i], i konumunda başlayıp tüm dizenin bir önekiyle de eşleşen en uzun alt dizenin uzunluğudur.
Küçük bir örnek
aabaab için z dizisi 0,1,0,3,1,0 olur. 3. dizindeki aab dizisi önekle eşleştiği için uzunluk 3'tür.
Z kutusu
Şimdiye kadar bulunan en sağdaki eşleşme olan bir [l, r] penceresini takip ederiz. Bu pencere, önceki karşılaştırmaları yeniden kullanmamızı sağlar.
l, r = 0, 0Kutunun içinde
i kutunun içindeyken, başlangıç noktası olarak bilinen bir z değerini kopyalarsınız; bu değer kutunun sınırıyla kısıtlanır.
if i < r:
z[i] = min(r - i, z[i - l])Kutunun dışına genişletme
Başlangıçtaki eşleşmeden sonra, önekle eşleştikleri sürece karakterleri tek tek karşılaştırmaya devam edersiniz.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Kutuyu ileri kaydırma
Eşleşmeniz daha sağa ulaşırsa, gelecekteki dizinlerin bu eşleşmeyi yeniden kullanabilmesi için l ve r değerlerini güncellersiniz.
if i + z[i] > r:
l, r = i, i + z[i]Doğrusal zaman garantisi
Kutu yalnızca sağa doğru ilerler; bu nedenle toplam iş O(n) olur. Her karakter sınırlı miktarda katkı sağlar.
Z ile arama
pattern + sep + text ifadelerini birleştirip Z algoritmasını çalıştırın. Desen uzunluğuna eşit olan her z değeri bir eşleşmedir.
combined = pattern + chr(0) + text
z = z_function(combined)Eşleşmeleri çıkarma
Z dizisini tarayın; z[i] == len(pattern) olan her yerde eşleşme, metindeki karşılık gelen konumda başlar.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z ve KMP
Z ve KMP'nin ikisi de doğrusal zamanda çalışır. Z'yi kodlamak çoğu zaman daha kolaydır; bu nedenle araç takımınızda harika bir yedek seçenektir.
Hızlı kontrol
Z dizisinin anlamını tam olarak kavradığınızdan emin olun.
Özet: Z işlevinin gücü
Kayan bir kutuyla Z dizisini oluşturdunuz, doğrusal zamanda arama yaptınız ve artık KMP'ye temiz bir alternatifiniz var. 🎯
Sıkça Sorulan Sorular
“Desen Araması için Z-İşlevi” dersi ücretsiz mi?
Evet — “Desen Araması için Z-İş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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Desen Araması için Z-İşlevi” dersinde ne öğreneceğim?
Dize boyunca önekleri eşleştirin. Coding Interview Prep 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, 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 3. dersidir.
“Desen Araması için Z-İş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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep 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.
Bu kursun tüm dersleri
- KMP Önek İşlevi
- Polinomsal Dize Hash'leme
- Desen Araması için Z-İşlevi
- Önek Aramaları için Trie'ler