الگوریتم جستجوی رشته رابین-کارپ
استفاده از درهم‌سازی

یک تابع درهم‌سازی، تابعی است که مجموعۀ بزرگی از داده‌ها را به مجموعۀ کوچکتری از داده‌ها نگاشت می‌کند. در اینجا تابع درهم‌سازی هر رشته را به یک مقدار عددی که به آن مقدار درهم‌سازی می‌گویند، تبدیل می‌کند. برای مثال اگر تابع را برابر طول رشته تعریف کنیم hash("hello") = 5 و hash("cat") = 3 خواهد بود.
الگوریتم رابین-کارپ با بهره‌گیری از این حقیقت که اگر دو رشته یکسان باشند، مقدار درهم‌سازی آن‌ها نیز با هم برابر خواهد بود، سعی دارد به جای مقایسه حرف یه حرف دو رشته، مقادیر درهم‌سازی آنان را مقایسه کند. برای این کار کافی است مقدار درهم‌سازی رشته الگو را حساب نماید و سپس در متن به دنبال زیررشته‌ای با مقدار درهم‌سازی برابر با آن بگردد.
نکته‌ای که باید به آن توجه کرد این است که رشته‌های مختلف می‌توانند مقادیر درهم‌سازی یکسان داشته باشند. به این رویداد تصادم  گفته می‌شود. مثلاً در مثال بالا مقدار درهم‌سازی هر رشتۀ پنج حرفی برابر 5 خواهد بود. پس با اینکه یکسان بودن دو رشته به معنای یکسان بودن مقدار درهم‌سازی آنان است اما عکس این موضوع لزوماً برقرار نیست.
در نتیجه در صورت برابر نبودن مقدار درهم‌سازی رشتۀ الگو و زیررشته قطعاً می‌توان نتیجه گرفت که خود رشته‌ها نیز با هم برابر نیستند ولی در صورت برابر بودن این دو مقدار لزوماً نمی‌توان برابری رشته‌ها را نتیجه گرفت (برابری مقدار درهم‌سازی شرط لازم است ولی کافی نیست و ممکن است دو رشته با مقدار درهم‌سازی برابر یافت کرده باشیم در حالی که اصل رشته‌ها برابر نیستند). پس در این حالت یکسان بودن زیررشته با رشتۀ الگو را باید با مقایسه حرف به حرف تحقیق کنیم. حال درصورتی که واقعاً تصادم رخ داده باشد (به رشته‌های متفاوت با مقدار درهم‌سازی یکسان برخورد کرده باشیم) این کار زمان اجرا را بیهوده افزایش داده است. خوشبختانه اگر تابع درهم‌سازی را خوب تعریف کنیم می‌توانیم امیدوار باشیم این رویداد زیاد رخ ندهد و زمان اجرای میانگین، مطلوب باشد.
تابع درهم‌سازی استفاده شده در رابین-کارپ به این صورت تعریف می‌شود:
hash(T[1 .. m]) = (T[1]×dm-1 + T[2]×dm-2 + ... + T[m]×d0) mod q
که در آن  d و  q دو مقدار ثابت هستند. اگر  \Sigma  مجموعۀ الفبا باشد،  d به طور معمول اینگونه تعریف می‌شود:
 d=\left|\Sigma \right| و  q نیز عموماً یک عدد اول بزرگ در نظر گرفته می‌شود به طوری که  qd در یک کلمه از کامپیوتر جا بگیرد.
برای مثال اگر فرض کنیم  \Sigma =\{0,1,2,...,9\}، متن موردنظر ما  T=''43141567'' و برای راحتی کار  q=1 باشد، خواهیم داشت:  d=10 و مقدار درهم‌سازی زیررشته "31415" به طول 5 از متن برابر است با:
( 3×104 + 1×103 + 4×102 + 1×101 + 5×100 ) mod 1 = 31415 mod 1 = 31415
مقدار تابع درهم‌سازی تعریف شده را برای هر رشته به طول m می‌توان با استفاده از روش هورنر در زمان  \Theta (m) به این صورت محاسبه کرد:
hash(T[1 .. m]) = (T[m] + d(T[m-1] + d(T[m-2] + ... + d(T[2] + dT[1])...)))  mod q
حال اگر بخواهیم برای هر زیررشته یک‌بار مقدار این تابع را حساب کنیم از آنجا که n-m+1 زیررشته داریم، این کار  \Theta (m(n-m+1)) طول می‌کشد که همان زمان اجرای الگوریتم ساده‌لوحانه می‌باشد و در حقیقت زمان اجرا بهبود نیافته است. برای حل این مشکل از درهم‌سازی چرخشی استفاده می‌کنیم. درهم‌سازی چرخشی به ما امکان می‌دهد تا مقدار درهم‌سازی زیررشتۀ هر مرحله را از روی مقدار درهم‌سازی زیررشتۀ مرحله قبلی در زمان ثابت به دست بیاوریم. این روند در حال کلی به صورت زیر است:
s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
در الگوریتم رابین-کارپ اگر مقدار درهم‌سازی زیررشته در مرحله s ام را  t_{s} بنامیم، رابطۀ درهم‌سازی چرخشی به این صورت خواهد بود:
ts+1 = ( d( ts - dm-1 T[s+1] ) + T[s+m+1] ) mod q
در مثال گفته شده در بالا اگر بخواهیم مقدار درهم‌سازی زیررشته مرحله بعد یعنی "14156" را از روی مقدار درهم‌سازی زیررشته قبل یعنی "31415" حساب کنیم روند کار به این صورت خواهد بود:
ts+1 = ( 10×(31415 - 104 × 3) + 6 ) mod 1 = 14156
در نهایت می‌توان گفت در الگوریتم رابین-کارپ کافی است تنها مقدار درهم‌سازی رشتۀ الگو [P[1..m و مقدار درهم‌سازی زیررشته [T[1..m از متن را در بخش پیش پردازش با زمان  \Theta (m) محاسبه کرد و سپس محاسبه مقادیر درهم‌سازی زیررشته‌های مراحل بعد در هر مرحله با زمان  \Theta (1) قابل انجام است.