Polinomsal Dize Hash'leme

Çoğu zaman iki alt dizenin eşit olup olmadığını sormanız gerekir. Karakter karakter karşılaştırmalar yavaştır; bu nedenle her dizeyi bir sayıya dönüştürürüz. 🔢

Bir karma, bir dizeyi tek bir tam sayıya dönüştürür. İki dize farklıysa karmaları da neredeyse her zaman farklı olur.

Her karakteri p tabanındaki bir rakam olarak okuruz. Bu polinom bakışı, dizeyi büyük bir ağırlıklı toplama dönüştürür.

31 gibi bir asal taban ve büyük bir asal modül seçin. Mod işlemi sayıları küçük tutar ve taşmayı önler.

Dizeyi dolaşın ve her karakteri Horner kuralıyla birleştirin; her adımda mod işlemi uygulayın.

Her konum için bir önek karması saklayın. Ardından herhangi bir alt dize karmasını hızlı bir çıkarmayla elde edebilirsiniz.

Ayrıca tabanın kuvvetlerini önceden hesaplayın. Çıkarma yaptığınızda iki öneki aynı ölçeğe getirirler.

s[l..r] alt dizesinin karması, bir kuvvetle ölçeklendirilmiş iki önek karmasının çıkarılmasıdır. Sorgu başına sabit zaman.

İki farklı dize aynı karma değerini paylaşabilir; buna çakışma denir. Bu durum nadirdir, ancak yarışmalarda bazen girdiler özellikle bunu tetikleyecek şekilde hazırlanır.

İki bağımsız modül kullanıp her iki karma değerini de karşılaştırın. İkisinde birden aynı anda çakışma olması pratikte imkânsızdır.

Karma işlemi alt dize karşılaştırmasını, tekrarları bulmayı ve desen aramayı mümkün kılar. Çok amaçlı, esnek bir araçtır.

Çok sayıda alt dizeyi güvenli biçimde karşılaştırmak için doğru aracı seçin.

Artık dizeleri polinom karma değerlerine dönüştürebilir, herhangi bir alt dizeyi O(1) sürede sorgulayabilir ve çakışmalara karşı önlem alabilirsiniz. 🚀