هش رولینگ (Rabin-Karp)
الگوریتم Rabin-Karp: جستجو با هش رولینگ — محاسبه هش پنجره بعدی در O(1) و مقایسه با KMP
ایده: هش به‌جای مقایسه
به‌جای مقایسه کاراکتر به کاراکتر، هش الگو و هر پنجره از متن را مقایسه کنیم — اعداد سریع‌تر از رشته مقایسه می‌شوند!
هش رولینگ — جادوی O(1)
هش پنجره بعدی را از قبلی بساز (مثل پنجره لغزان!):
هش جدید = (هش قبلی − کاراکتر_خروجی × base^(m-1)) × base + کاراکتر_ورودیمثل عدد: «123» ← «234» = (123 − 1×100) × 10 + 4. هر پنجره فقط O(1)!
الگوریتم
- هش الگو و پنجره اول متن را حساب کن
- پنجره را لغزان بده؛ هش را O(1) به‌روزرسانی کن
- هش برابر؟ مقایسه واقعی کن (ضد برخورد!)
چرا مقایسه واقعی لازم است؟
هش‌های متفاوت = قطعاً متفاوت؛ اما هش برابر ≠ قطعاً برابر (برخورد!). پس بعد از تطابق هش، کاراکترها را چک می‌کنیم. با هش خوب، برخورد نادر و میانگین O(n+m).
مدیریت اعداد بزرگ: mod
هش رشته بلند خیلی بزرگ می‌شود؛ با mod عدد اول بزرگ (مثل 10⁹+7) کوچک نگه می‌داریم — و برخورد را نادر.
KMP یا Rabin-Karp؟
| ویژگی | KMP | Rabin-Karp |
|---|---|---|
| بدترین حالت | O(n+m) تضمینی ✓ | O(n×m) (برخورد زیاد) |
| میانگین | O(n+m) | O(n+m) ✓ |
| پیاده‌سازی | پیچیده‌تر (LPS) | ساده‌تر ✓ |
| جستجوی چند الگو | سخت | عالی ✓ (هش مجموعه) |
| تشخیص سرقت ادبی | — | ✓✓ (تقسیم به پنجره‌ها) |
کاربرد ویژه: چند الگو هم‌زمان
وقتی چند الگو دارید (مثل فیلتر کلمات)، هش همه را در مجموعه بگذارید و پنجره‌ها را یک‌بار چک کنید — جایی که KMP باید جدا برای هر الگو اجرا شود!
جمع‌بندی
- هش رولینگ: پنجره بعدی از قبلی در O(1)
- هش برابر ← مقایسه واقعی (ضد برخورد)
- میانگین O(n+m)؛ ساده و قابل توسعه
- قهرمان: چند الگو و تشخیص تکرار اسناد
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.