Bu yazıda metin içinde yazı aramada kullanılan bu algoritmayı basitçe tanıtıp simülasyonunu göstereceğim. Basit yazı arama algoritmasında her adımda aradığımız yazıyı metin üzerinde kaydırıp tek tek aynı pozisyonda aynı harflerin olup olmadığına bakmıştık. Yani aradığımız yazıyı bulana kadar her adımda ilk farklı harfe rastlayana kadar her harfi defalarca karşılaştırmıştık.
Bu algoritmada aynı harfleri defalarca karşılaştırma sorununa ilginç bir çözüm sunuluyor. Rolling hash denen bu algoritmayı daha önceki yazımda ele alıp simülasyonunu vermiştim. Kabaca aynı yazı parçalarının hash değerleri aynı olmalıdır fikrinden yola çıkılarap geliştirilmiş bir algoritma bu rabin-karp algoritması. Tabii ki her adımda kaydırılmış yazı parçalarının hash değerlerini tekrar tekrar her harfi kullanarak hesaplamamak için rolling hash kullanılıyor. Metinde aranan parça ile aynı hash değerini veren bir parça bulunduğunda bu parçanın harflerini tek tek karşılaştırmak gerekiyor çünkü farklı metin parçaları aynı hash değerlerini üretebilir.
Simülasyonda da bunu yapıyorum. Her kaydırmadan kontrol edilen metin parçası gri renkle işaretleniyor. İlk adımda hash değeri bütün harf değerleri üzerinden hesaplanıyor. Ardından her kaydırmada rollin hash algoritması kullanılarak yeni parçanın hash değeri daha hızlı hesaplanıyor. Eğer bir yerde aynı hash değerleri bulunursa bu sefer o alt parçanın bütün harfleri aranan yazının harfleriyle tek tek karşılaştırılıyor. Eğer harfler aynı ise bu harf yeşile boyanıyor, değilse kırmızı. Bütün harfler yeşil ise o zaman aradığımız yazıyı bulduk demektir ve algoritma sonlanıyor.
Bu linkten simülasyonu kullanabilirsiniz.