====== الگوریتم رابین-کارپ ======

===== تعریف =====

یکی از مسائلی که در زمینه‌های مختلف مرتبط با کامپوتر مطرح است،‌ مسائل مربوط به پیدا کردن یک رشته (عموما نه چندان بلند) در میان یک رشته‌ی بسیار بلند است. به صورت دقیق‌تر، فرض کنید می‌خواهیم یک رشته‌ی $m$ حرفی را در یک رشته‌ی $n$ حرفی به صورت یک زیررشته‌ی متوالی پیدا کنیم. پیاده‌سازی بدیهی چنین جستجویی،‌ دارای پیچیدگی زمانی $O(nm)$ خواهد بود. الگوریتم رابین - کارپ با استفاده از تکنیک [[آموزش:الگوریتم:درهم‌سازی|درهم‌سازی]] این مسئله را در پیچیدگی زمانی $O(n + m)$ حل می‌کند.


===== الگوریتم =====

فرض کنید یک زیررشته‌ی متوالی شامل حروف $i$ تا $j$ یک رشته رابا $s[i..j]$ نشان دهیم. فرض کنید بخواهیم رشته‌ی $s$ را در $t$ پیدا کنیم. الگوریتم جستجو به شکل زیر عمل می‌کند:

به ازای هر $i$، زیررشته‌ی $s[i..i + m - 1]$ را با $t$ مقایسه کنید و در صورت برابر بودن این زیررشته را به عنوان یک نسخه از $t$ در $s$ گزارش کنید.

اگر زمان مقایسه‌ی دو رشته به طول $x$ را با $f(x)$ نشان دهیم الگوریتم در $O(f(x) * n)$ انجام می‌شود. در حالت عادی $f(x) = O(m)$. الگوریتم رابین‌کارپ روشی برای مقایسه‌ی دو رشته ارائه می‌دهد که به صورت متوسط $f(x) = O(1)$. هر چند در واقع در بدترین حالت یک جستجو می‌تواند زمان $O(m)$ طول بکشد اما چنین اتفاقی با احتمال کمی رخ می‌دهد. 

الگوریتم رابین‌کارپ جستجو را به این گونه تغییر می‌دهد که پیش از مقایسه‌ی دو رشته در $O(m)$ ابتدا مقدار یک تابع درهم‌ساز را برای آن‌ها محاسبه کرده و تنها در صورت برابری این مقایسه را انجام می‌دهد. نکته‌ی الگوریتم رابین‌کارپ محاسبه‌ی این تابع به گونه‌ای است که در مجموع در زمان $O(n + m)$ قابل انجام است. بعلاوه با وجود اینکه احتمال برابری تابع درهم‌ساز برای دو رشته‌ی نابرابر وجود دارد، این احتمال برای تابع درهم‌ساز مورد استفاده کم است.



===== پیاده‌سازی اولیه =====

<code c A.c>
function NaiveSearch(string s[1..n], string pattern[1..m])

   for i from 1 to n-m+1

      for j from 1 to m

         if s[i+j-1] ≠ pattern[j]

            jump to next iteration of outer loop

      return i

   return not found
</code>


===== پیاده‌سازی سریع‌تر =====

<code c ‌‌B.c>
function RabinKarp(string s[1..n], string pattern[1..m])

  hpattern := hash(pattern[1..m]);

  for i from 1 to n-m+1

    hs := hash(s[i..i+m-1])

    if hs = hpattern

      if s[i..i+m-1] = pattern[1..m]

        return i

  return not found
</code>


===== تابع درهم‌ساز =====

تابع درهم‌ساز «اثر انگشت رابین» تابعی است که در این الگوریتم برای درهم‌سازی رشته‌ها استفاده می‌شود. این الگوریتم هر زیررشته را معادل یک عدد در یک مبنای ثابت در نظر می‌گیرد. مبنای مورد استفاده معمولا یک عدد اول بزرگ است. در این الگوریتم هر حرف معادل یک رقم است و مقدار آن برابر کد ASCII آن حرف در نظر گرفته می‌شود. برای مثال :
<code>
// ASCII a = 97, b = 98, r = 114. 
hash("abr") = (97 × 1012) + (98 × 1011) + (114 × 1010) = 999,509 
</code>
نکته‌ی این الگوریتم آن است که اگر مقدار آن برای زیررشته‌ی $s[i..j]$ محاسبه شده باشد، مقدار آن برای زیررشته‌ی $s[i + 1..j + 1]$ در $O(1)$ قابل محاسبه است. برای مثال اگر $s = abracadabra$ می‌توان از روی مقدار hash("abr") مقدار hash("bra") را به شکل زیر محاسبه کرد:
<code>
//             base   old hash    old 'a'         new 'a'
hash("bra") = [1011 × (999,509 - (97 × 1012))] + (97 × 1010) = 1,011,309

</code>

پس بنابراین در الگوریتم مقایسه‌ی بالا، کافی است در ابتدا در $O(m)$ مقدار تابع برای $s[1..m]$ را محاسبه کرد و پس از آن در هرمرحله مقدار تابع برای $s[i..i + m - 1]$ را از روی مقدار تابع برای $s[i - 1..i + m - 2]$ محاسبه کرد. در این صورت پیچیدگی زمانی از $O(n + m)$ خواهد بود.

===== مراجع =====

  * [[https://en.wikipedia.org/wiki/Rabin–Karp_algorithm|Wikipedia]]