Rabin–Karp یکی از الگوریتم‌های کلاسیک برای پیدا کردن یک Pattern داخل یک Text است.

برخلاف روش ساده که در هر موقعیت Pattern را کاراکتر به کاراکتر با Text مقایسه می‌کند، Rabin–Karp ابتدا از Pattern یک Hash می‌سازد و سپس Hash بخش‌های هم‌اندازه Text را با آن مقایسه می‌کند.

ایده اصلی را می‌توان در یک جمله خلاصه کرد:

به جای مقایسه کامل رشته‌ها در هر موقعیت، ابتدا Hash آن‌ها را مقایسه کن و فقط وقتی Hashها برابر شدند، مقایسه دقیق انجام بده.

این الگوریتم به‌خصوص زمانی جالب می‌شود که مفهوم Rolling Hash را وارد کنیم؛ یعنی بتوانیم Hash پنجره بعدی Text را بدون محاسبه مجدد تمام کاراکترهای آن به دست آوریم.

مسئله String Matching

فرض کنید Text زیر را داریم:

ABCCDDAEFG

و می‌خواهیم Pattern زیر را پیدا کنیم:

CDD

روش Naive می‌تواند Pattern را روی موقعیت‌های مختلف Text قرار دهد:

ABC
 BCC
  CCD
   CDD  ← Match

در هر موقعیت چند کاراکتر با Pattern مقایسه می‌شوند.

Rabin–Karp تلاش می‌کند این مقایسه‌ها را با Hash کاهش دهد.

Hash در Rabin–Karp چه نقشی دارد؟

فرض کنید بتوانیم هر رشته را به یک مقدار عددی تبدیل کنیم:

"ABC" → 12345
"BCD" → 48320
"CDD" → 79152

اگر Hash Pattern برابر باشد با:

فقط Windowهایی از Text که Hash آن‌ها نیز 79152 است Candidate محسوب می‌شوند.

مثلاً:

Hash("CCD") != Hash("CDD")

پس لازم نیست تمام کاراکترهای آن‌ها را دقیق بررسی کنیم.

اما اگر:

Hash(window) == Hash(pattern)

شد، هنوز نمی‌توانیم صددرصد مطمئن باشیم که رشته‌ها برابرند.

چرا؟

به دلیل Hash Collision.

Hash Collision چیست؟

Hash Function تعداد محدودی خروجی دارد، اما تعداد رشته‌های ممکن بسیار زیاد است.

بنابراین ممکن است دو رشته متفاوت Hash یکسانی داشته باشند.

مثلاً به صورت فرضی:

Hash("ABC") = 105
Hash("XYZ") = 105

در نتیجه در Rabin–Karp وقتی Hashها برابر می‌شوند، باید یک مقایسه نهایی انجام دهیم:

Hash Match
↓
Compare actual characters
↓
Real Match or Collision

به این مرحله معمولاً Verification گفته می‌شود.

Rolling Hash چیست؟

Rolling Hash مهم‌ترین ایده Rabin–Karp است.

فرض کنید Window فعلی Text این باشد:

ABC

و Window بعدی:

BCD

به جای اینکه Hash BCD را از صفر محاسبه کنیم، می‌توانیم:

اثر A را از Hash قبلی حذف کنیم.
Window را یک موقعیت Shift کنیم.
اثر D را اضافه کنیم.

یعنی:

ABC
 ↓ shift
BCD

این کار باعث می‌شود Hash هر Window جدید تقریباً در زمان ثابت محاسبه شود.

ساخت Hash به صورت عددی

یکی از روش‌های رایج استفاده از Polynomial Rolling Hash است.

برای رشته‌ای مانند:

ABC

می‌توانیم چیزی شبیه این داشته باشیم:

A × base² + B × base¹ + C × base⁰

که در آن A، B و C مقدار عددی کاراکترها هستند.

برای جلوگیری از بسیار بزرگ شدن اعداد از Modulo استفاده می‌کنیم:

hash = hash % prime

پس Hash معمولاً شکلی شبیه این دارد:

hash = (
  c0 × base^(m-1) +
  c1 × base^(m-2) +
  ... +
  cm-1
) % prime

Base و Prime چیستند؟

در بسیاری از پیاده‌سازی‌ها دو مقدار داریم:

base
prime

base معمولاً نماینده اندازه Alphabet یا یک عدد مناسب برای ترکیب کاراکترها است.

مثلاً:

base = 256

و برای Modulo از یک عدد Prime استفاده می‌شود:

prime = 101

در سیستم‌های واقعی انتخاب Hash Function مناسب اهمیت زیادی دارد، زیرا Hash ضعیف می‌تواند Collision زیادی ایجاد کند.

الگوریتم Rabin–Karp مرحله‌به‌مرحله

فرض کنیم:

Text = "ABCCDDAEFG"
Pattern = "CDD"

طول Pattern:

m = 3

ابتدا محاسبه می‌کنیم:

Pattern Hash = Hash("CDD")

و Hash اولین Window از Text:

Window Hash = Hash("ABC")

اگر برابر نبودند، Window را Shift می‌کنیم:

ABC
 ↓
BCC
 ↓
CCD
 ↓
CDD

در هر Shift، به جای محاسبه کامل Hash از Rolling Hash استفاده می‌کنیم.

وقتی Hash CDD با Hash Pattern برابر شد، یک مقایسه کاراکتری انجام می‌دهیم.

اگر برابر باشند، Pattern پیدا شده است.

شبه‌کد Rabin–Karp

patternHash = hash(pattern)
windowHash  = hash(first window of text)

for each window:
    if patternHash == windowHash:
        if pattern == currentWindow:
            return index

    update windowHash using rolling hash

return -1

این ساختار ساده، هسته اصلی الگوریتم است.

پیاده‌سازی Rabin–Karp با TypeScript

function rabinKarp(
  text: string,
  pattern: string
): number {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (patternHash === windowHash) {
      let matches = true;

      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          matches = false;
          break;
        }
      }

      if (matches) {
        return i;
      }
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return -1;
}

مثال:

console.log(
  rabinKarp("ABCCDDAEFG", "CDD")
);

خروجی:

یعنی Pattern از Index شماره 3 شروع شده است.

Rolling Hash چگونه Update می‌شود؟

فرض کنید Window قبلی:

ABC

باشد و بخواهیم به:

BCD

برویم.

به صورت مفهومی:

oldHash
↓
remove A contribution
↓
shift remaining characters
↓
add D
↓
newHash

فرمول کلی می‌تواند چیزی شبیه این باشد:

newHash = (
  base × (
    oldHash - oldChar × highOrder
  ) + newChar
) % prime

highOrder نماینده وزن کاراکتر اول Window است.

چرا windowHash ممکن است منفی شود؟

در JavaScript و بسیاری از زبان‌ها، عمل % روی عدد منفی ممکن است نتیجه منفی بدهد.

مثلاً:

-5 % 101

می‌تواند منفی باشد.

به همین دلیل بعد از Update معمولاً می‌نویسیم:

if (windowHash < 0) {
  windowHash += prime;
}

تا Hash در محدوده مورد انتظار باقی بماند.

پیچیدگی زمانی Rabin–Karp

اگر طول Text برابر n و Pattern برابر m باشد، در حالت معمول Rolling Hash باعث می‌شود بررسی Windowها بسیار سریع انجام شود.

Average Case:

O(n + m)

یا معمولاً به صورت ساده:

O(n)

بعد از ساخت Hash Pattern.

اما Worst Case می‌تواند باشد:

O(n × m)

چرا؟

اگر Collisionهای زیادی رخ دهند، ممکن است برای تعداد زیادی Window مجبور شویم Pattern را کاراکتر به کاراکتر Verify کنیم.

Space Complexity

در نسخه ساده Rabin–Karp فقط چند متغیر Hash نگهداری می‌شوند.

پس:

Space Complexity: O(1)

بدون در نظر گرفتن فضای ورودی.

Rabin–Karp در برابر Naive Search

Naive Search در بدترین حالت:

O(n × m)

است.

Rabin–Karp در حالت متوسط با Rolling Hash:

O(n + m)

رفتار می‌کند.

اما تفاوت مهم این است که Rabin–Karp به Hash Function وابسته است و ممکن است Collision داشته باشد.

Rabin–Karp در برابر KMP

هر دو برای String Matching استفاده می‌شوند، اما ایده آن‌ها کاملاً متفاوت است.

KMP

از ساختار داخلی Pattern استفاده می‌کند:

LPS
Prefix / Suffix

و تضمین می‌کند:

O(n + m)

Rabin–Karp

از Hash استفاده می‌کند:

Rolling Hash
Hash Comparison
Verification

Average Case بسیار خوب است، اما Worst Case می‌تواند به O(n × m) برسد.

چه زمانی Rabin–Karp جذاب‌تر است؟

Rabin–Karp زمانی بسیار جالب می‌شود که بخواهیم چند Pattern را همزمان بررسی کنیم.

فرض کنید می‌خواهیم هزاران Pattern هم‌اندازه را داخل Text پیدا کنیم.

می‌توانیم Hash Patternها را در یک Set ذخیره کنیم:

Pattern Hashes
├── 10521
├── 83442
├── 99301
└── ...

سپس Hash هر Window از Text را محاسبه کنیم و بررسی کنیم آیا در Set وجود دارد یا خیر.

این یکی از مزیت‌های مهم Hash-based Matching است.

کاربرد در Plagiarism Detection

یکی از کاربردهای مفهومی Rolling Hash بررسی بخش‌های مشترک Documentها است.

به جای مقایسه مستقیم تمام Substringها، می‌توانیم Document را به Windowهایی تقسیم کنیم و Hash آن‌ها را محاسبه کنیم.

مثلاً:

Document A
↓
5-word windows
↓
Hashes

و سپس Hashهای Document دوم را مقایسه کنیم.

این ایده در تکنیک‌هایی مانند Fingerprinting و Similarity Detection توسعه پیدا می‌کند.

البته سیستم‌های واقعی Plagiarism Detection معمولاً از روش‌های پیچیده‌تر نیز استفاده می‌کنند.

کاربرد در Duplicate Content Detection

فرض کنید می‌خواهیم بخش‌های تکراری را در حجم زیادی از Text پیدا کنیم.

Rolling Hash می‌تواند برای Hash کردن Windowهای متوالی استفاده شود.

اگر Hash دو Window برابر باشد، آن‌ها Candidate مقایسه دقیق می‌شوند.

این روش در:

Duplicate Detection
Document Similarity
File Comparison
Text Processing

کاربرد مفهومی دارد.

کاربرد در DNA Sequence Search

Sequenceهای DNA نیز می‌توانند به صورت String نمایش داده شوند:

ACGTACGTACGT

اگر به دنبال Pattern خاصی باشیم:

TACG

می‌توان از String Matching و Rolling Hash استفاده کرد.

در کاربردهای واقعی Bioinformatics معمولاً الگوریتم‌های تخصصی‌تر نیز استفاده می‌شوند، اما Rabin–Karp مثال خوبی برای درک Hash-based Sequence Matching است.

کاربرد در Malware و Signature Detection

فرض کنید Stream یا File بزرگی داریم و می‌خواهیم Signatureهای شناخته‌شده را بررسی کنیم.

اگر Signatureها طول مشخصی داشته باشند، Hash-based Matching می‌تواند Candidateها را سریع فیلتر کند.

ساختار مفهومی:

Data Stream
↓
Sliding Windows
↓
Rolling Hash
↓
Known Signature Hashes
↓
Verification

در سیستم‌های امنیتی واقعی، روش‌ها بسیار پیچیده‌تر هستند، اما این مدل ایده اصلی را نشان می‌دهد.

کاربرد در Data Deduplication

در Data Processing ممکن است بخواهیم Chunkهای تکراری را شناسایی کنیم.

برای مثال:

Chunk A → Hash X
Chunk B → Hash Y
Chunk C → Hash X

Chunk A و C Candidateهای Duplicate هستند.

البته برای جلوگیری از خطا، Equality نهایی نباید صرفاً بر Hash تکیه کند، مگر اینکه مدل Hash و احتمال Collision متناسب با سیستم طراحی شده باشد.

Double Hashing چیست؟

یکی از راه‌های کاهش احتمال Collision استفاده از دو Hash مستقل است.

مثلاً:

hash1 using prime1
hash2 using prime2

دو Window فقط زمانی Candidate Match محسوب می‌شوند که:

hash1 equal
AND
hash2 equal

باشد.

به این تکنیک معمولاً Double Hashing گفته می‌شود.

احتمال Collision در این حالت به شکل قابل توجهی کاهش پیدا می‌کند.

Rolling Hash در مسائل دیگر

Rolling Hash فقط برای Rabin–Karp نیست.

این تکنیک در مسائل مختلفی دیده می‌شود:

Longest Duplicate Substring
Repeated Substring Search
String Similarity
Substring Equality Queries
Document Fingerprinting
Competitive Programming

در بسیاری از این مسائل، Hash Prefixها یا Windowهای متوالی محاسبه می‌شود.

Prefix Hash چیست؟

به جای Rolling Hash مستقیم می‌توان Hash Prefixها را از قبل محاسبه کرد.

مثلاً:

prefixHash[i]

Hash کاراکترهای ابتدای String تا موقعیت i را ذخیره می‌کند.

سپس Hash یک Substring را می‌توان با محاسبات ریاضی از دو Prefix Hash به دست آورد.

این تکنیک زمانی مفید است که تعداد زیادی Query روی یک String ثابت داشته باشیم.

سؤال رایج مصاحبه

صورت مسئله می‌تواند چنین باشد:

Pattern را در Text با استفاده از Rolling Hash پیدا کنید.

یا:

تمام Occurrenceهای Pattern را پیدا کنید.

یک پاسخ خوب باید شامل این موارد باشد:

Hash Pattern.
Hash اولین Window.
Rolling Update.
Hash Comparison.
Verification برای جلوگیری از Collision.
تحلیل Average و Worst Case.

پیدا کردن تمام Matchها

نسخه‌ای که تمام Indexها را برمی‌گرداند:

function rabinKarpAll(
  text: string,
  pattern: string
): number[] {
  const result: number[] = [];

  const n = text.length;
  const m = pattern.length;

  if (m === 0 || m > n) {
    return result;
  }

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (
      patternHash === windowHash &&
      text.slice(i, i + m) === pattern
    ) {
      result.push(i);
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return result;
}

مثلاً:

rabinKarpAll("AAAAA", "AA");

خروجی:

[0, 1, 2, 3]

اشتباهات رایج

1. اعتماد کامل به Hash

این شرط کافی نیست:

patternHash === windowHash

در نسخه‌ای که Hash Collision امکان‌پذیر است باید Verification انجام شود.

2. محاسبه Hash از صفر برای هر Window

اگر در هر موقعیت تمام Pattern را دوباره Hash کنیم، مزیت اصلی Rabin–Karp را از دست می‌دهیم.

هدف Rolling Hash این است که Update پنجره سریع باشد.

3. فراموش کردن Modulo

بدون Modulo مقادیر Hash می‌توانند بسیار بزرگ شوند و در JavaScript حتی با مسئله Precision روبه‌رو شویم.

4. انتخاب Hash ضعیف

Prime یا Base نامناسب می‌تواند Collision را افزایش دهد.

برای سیستم‌های Production باید Hash Strategy با دقت بیشتری طراحی شود.

5. اشتباه در حذف کاراکتر قدیمی

برای حذف اولین کاراکتر Window باید وزن صحیح آن را در Polynomial Hash بدانیم.

به همین دلیل highOrder را از قبل محاسبه می‌کنیم.

Edge Caseها

Pattern خالی

بسته به قرارداد می‌توان 0 یا لیست خالی برگرداند.

Pattern بزرگ‌تر از Text

Text = "abc"
Pattern = "abcdef"

هیچ Matchی وجود ندارد.

Text و Pattern برابر

algorithm
algorithm

نتیجه Index صفر است.

Matchهای هم‌پوشان

AAAAA
AA

Matchها:

0, 1, 2, 3

الگوریتم باید در صورت نیاز Overlapها را نیز در نظر بگیرد.

چه زمانی از Rabin–Karp استفاده کنیم؟

Rabin–Karp انتخاب مناسبی است وقتی:

می‌خواهیم Rolling Hash را یاد بگیریم.
تعداد زیادی Window متوالی داریم.
چند Pattern هم‌اندازه را بررسی می‌کنیم.
Hash-based filtering مفید است.
مسئله شامل Duplicate Substring یا Substring Hashing است.

اما برای یک Search ساده در Application Code معمولاً بهتر است از APIهای استاندارد زبان استفاده کنیم.

مثلاً:

text.indexOf(pattern)

یا:

text.includes(pattern)

Rabin–Karp در مصاحبه چه چیزی را می‌سنجد؟

معمولاً هدف فقط حفظ کردن کد نیست.

این الگوریتم چند مفهوم مهم را همزمان بررسی می‌کند:

Hashing
Sliding Window
Modular Arithmetic
String Matching
Collision Handling
Complexity Analysis

به همین دلیل از نظر آموزشی الگوریتم ارزشمندی است.

جمع‌بندی

Rabin–Karp الگوریتمی برای String Matching است که از Hash برای کاهش مقایسه‌های مستقیم استفاده می‌کند.

ساختار اصلی آن:

Pattern
↓
Hash

Text
↓
Sliding Window
↓
Rolling Hash
↓
Compare Hash
↓
Verify if equal

ویژگی‌های مهم:

Average Time: O(n + m)
Worst Time:   O(n × m)
Space:        O(1)

مهم‌ترین ایده‌ای که باید از Rabin–Karp به خاطر سپرد، خود String Search نیست؛ بلکه Rolling Hash است.

Rolling Hash به ما اجازه می‌دهد Hash یک Window جدید را با استفاده از Hash Window قبلی به‌روزرسانی کنیم، بدون اینکه تمام محتویات Window را از ابتدا پردازش کنیم.

همین مفهوم در مسائل پیشرفته‌تر مانند Duplicate Detection، Fingerprinting، Substring Queries و بسیاری از مسائل الگوریتمی دیگر نیز کاربرد دارد.

Rabin–Karp یکی از الگوریتم‌های کلاسیک برای پیدا کردن یک Pattern داخل یک Text است.

ایده اصلی را می‌توان در یک جمله خلاصه کرد:

به جای مقایسه کامل رشته‌ها در هر موقعیت، ابتدا Hash آن‌ها را مقایسه کن و فقط وقتی Hashها برابر شدند، مقایسه دقیق انجام بده.

مسئله String Matching

فرض کنید Text زیر را داریم:

ABCCDDAEFG

و می‌خواهیم Pattern زیر را پیدا کنیم:

CDD

روش Naive می‌تواند Pattern را روی موقعیت‌های مختلف Text قرار دهد:

ABC
 BCC
  CCD
   CDD  ← Match

در هر موقعیت چند کاراکتر با Pattern مقایسه می‌شوند.

Rabin–Karp تلاش می‌کند این مقایسه‌ها را با Hash کاهش دهد.

Hash در Rabin–Karp چه نقشی دارد؟

فرض کنید بتوانیم هر رشته را به یک مقدار عددی تبدیل کنیم:

"ABC" → 12345
"BCD" → 48320
"CDD" → 79152

اگر Hash Pattern برابر باشد با:

فقط Windowهایی از Text که Hash آن‌ها نیز 79152 است Candidate محسوب می‌شوند.

مثلاً:

Hash("CCD") != Hash("CDD")

پس لازم نیست تمام کاراکترهای آن‌ها را دقیق بررسی کنیم.

اما اگر:

Hash(window) == Hash(pattern)

شد، هنوز نمی‌توانیم صددرصد مطمئن باشیم که رشته‌ها برابرند.

چرا؟

به دلیل Hash Collision.

Hash Collision چیست؟

Hash Function تعداد محدودی خروجی دارد، اما تعداد رشته‌های ممکن بسیار زیاد است.

بنابراین ممکن است دو رشته متفاوت Hash یکسانی داشته باشند.

مثلاً به صورت فرضی:

Hash("ABC") = 105
Hash("XYZ") = 105

در نتیجه در Rabin–Karp وقتی Hashها برابر می‌شوند، باید یک مقایسه نهایی انجام دهیم:

Hash Match
↓
Compare actual characters
↓
Real Match or Collision

به این مرحله معمولاً Verification گفته می‌شود.

Rolling Hash چیست؟

Rolling Hash مهم‌ترین ایده Rabin–Karp است.

فرض کنید Window فعلی Text این باشد:

ABC

و Window بعدی:

BCD

به جای اینکه Hash BCD را از صفر محاسبه کنیم، می‌توانیم:

اثر A را از Hash قبلی حذف کنیم.
Window را یک موقعیت Shift کنیم.
اثر D را اضافه کنیم.

یعنی:

ABC
 ↓ shift
BCD

این کار باعث می‌شود Hash هر Window جدید تقریباً در زمان ثابت محاسبه شود.

ساخت Hash به صورت عددی

یکی از روش‌های رایج استفاده از Polynomial Rolling Hash است.

برای رشته‌ای مانند:

ABC

می‌توانیم چیزی شبیه این داشته باشیم:

A × base² + B × base¹ + C × base⁰

که در آن A، B و C مقدار عددی کاراکترها هستند.

برای جلوگیری از بسیار بزرگ شدن اعداد از Modulo استفاده می‌کنیم:

hash = hash % prime

پس Hash معمولاً شکلی شبیه این دارد:

hash = (
  c0 × base^(m-1) +
  c1 × base^(m-2) +
  ... +
  cm-1
) % prime

Base و Prime چیستند؟

در بسیاری از پیاده‌سازی‌ها دو مقدار داریم:

base
prime

base معمولاً نماینده اندازه Alphabet یا یک عدد مناسب برای ترکیب کاراکترها است.

مثلاً:

base = 256

و برای Modulo از یک عدد Prime استفاده می‌شود:

prime = 101

در سیستم‌های واقعی انتخاب Hash Function مناسب اهمیت زیادی دارد، زیرا Hash ضعیف می‌تواند Collision زیادی ایجاد کند.

الگوریتم Rabin–Karp مرحله‌به‌مرحله

فرض کنیم:

Text = "ABCCDDAEFG"
Pattern = "CDD"

طول Pattern:

m = 3

ابتدا محاسبه می‌کنیم:

Pattern Hash = Hash("CDD")

و Hash اولین Window از Text:

Window Hash = Hash("ABC")

اگر برابر نبودند، Window را Shift می‌کنیم:

ABC
 ↓
BCC
 ↓
CCD
 ↓
CDD

در هر Shift، به جای محاسبه کامل Hash از Rolling Hash استفاده می‌کنیم.

وقتی Hash CDD با Hash Pattern برابر شد، یک مقایسه کاراکتری انجام می‌دهیم.

اگر برابر باشند، Pattern پیدا شده است.

شبه‌کد Rabin–Karp

patternHash = hash(pattern)
windowHash  = hash(first window of text)

for each window:
    if patternHash == windowHash:
        if pattern == currentWindow:
            return index

    update windowHash using rolling hash

return -1

این ساختار ساده، هسته اصلی الگوریتم است.

پیاده‌سازی Rabin–Karp با TypeScript

function rabinKarp(
  text: string,
  pattern: string
): number {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (patternHash === windowHash) {
      let matches = true;

      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          matches = false;
          break;
        }
      }

      if (matches) {
        return i;
      }
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return -1;
}

مثال:

console.log(
  rabinKarp("ABCCDDAEFG", "CDD")
);

خروجی:

یعنی Pattern از Index شماره 3 شروع شده است.

Rolling Hash چگونه Update می‌شود؟

فرض کنید Window قبلی:

ABC

باشد و بخواهیم به:

BCD

برویم.

به صورت مفهومی:

oldHash
↓
remove A contribution
↓
shift remaining characters
↓
add D
↓
newHash

فرمول کلی می‌تواند چیزی شبیه این باشد:

newHash = (
  base × (
    oldHash - oldChar × highOrder
  ) + newChar
) % prime

highOrder نماینده وزن کاراکتر اول Window است.

چرا windowHash ممکن است منفی شود؟

در JavaScript و بسیاری از زبان‌ها، عمل % روی عدد منفی ممکن است نتیجه منفی بدهد.

مثلاً:

-5 % 101

می‌تواند منفی باشد.

به همین دلیل بعد از Update معمولاً می‌نویسیم:

if (windowHash < 0) {
  windowHash += prime;
}

تا Hash در محدوده مورد انتظار باقی بماند.

پیچیدگی زمانی Rabin–Karp

اگر طول Text برابر n و Pattern برابر m باشد، در حالت معمول Rolling Hash باعث می‌شود بررسی Windowها بسیار سریع انجام شود.

Average Case:

O(n + m)

یا معمولاً به صورت ساده:

O(n)

بعد از ساخت Hash Pattern.

اما Worst Case می‌تواند باشد:

O(n × m)

چرا؟

اگر Collisionهای زیادی رخ دهند، ممکن است برای تعداد زیادی Window مجبور شویم Pattern را کاراکتر به کاراکتر Verify کنیم.

Space Complexity

در نسخه ساده Rabin–Karp فقط چند متغیر Hash نگهداری می‌شوند.

پس:

Space Complexity: O(1)

بدون در نظر گرفتن فضای ورودی.

Rabin–Karp در برابر Naive Search

Naive Search در بدترین حالت:

O(n × m)

است.

Rabin–Karp در حالت متوسط با Rolling Hash:

O(n + m)

رفتار می‌کند.

اما تفاوت مهم این است که Rabin–Karp به Hash Function وابسته است و ممکن است Collision داشته باشد.

Rabin–Karp در برابر KMP

هر دو برای String Matching استفاده می‌شوند، اما ایده آن‌ها کاملاً متفاوت است.

KMP

از ساختار داخلی Pattern استفاده می‌کند:

LPS
Prefix / Suffix

و تضمین می‌کند:

O(n + m)

Rabin–Karp

از Hash استفاده می‌کند:

Rolling Hash
Hash Comparison
Verification

Average Case بسیار خوب است، اما Worst Case می‌تواند به O(n × m) برسد.

چه زمانی Rabin–Karp جذاب‌تر است؟

Rabin–Karp زمانی بسیار جالب می‌شود که بخواهیم چند Pattern را همزمان بررسی کنیم.

فرض کنید می‌خواهیم هزاران Pattern هم‌اندازه را داخل Text پیدا کنیم.

می‌توانیم Hash Patternها را در یک Set ذخیره کنیم:

Pattern Hashes
├── 10521
├── 83442
├── 99301
└── ...

سپس Hash هر Window از Text را محاسبه کنیم و بررسی کنیم آیا در Set وجود دارد یا خیر.

این یکی از مزیت‌های مهم Hash-based Matching است.

کاربرد در Plagiarism Detection

یکی از کاربردهای مفهومی Rolling Hash بررسی بخش‌های مشترک Documentها است.

به جای مقایسه مستقیم تمام Substringها، می‌توانیم Document را به Windowهایی تقسیم کنیم و Hash آن‌ها را محاسبه کنیم.

مثلاً:

Document A
↓
5-word windows
↓
Hashes

و سپس Hashهای Document دوم را مقایسه کنیم.

این ایده در تکنیک‌هایی مانند Fingerprinting و Similarity Detection توسعه پیدا می‌کند.

البته سیستم‌های واقعی Plagiarism Detection معمولاً از روش‌های پیچیده‌تر نیز استفاده می‌کنند.

کاربرد در Duplicate Content Detection

فرض کنید می‌خواهیم بخش‌های تکراری را در حجم زیادی از Text پیدا کنیم.

Rolling Hash می‌تواند برای Hash کردن Windowهای متوالی استفاده شود.

اگر Hash دو Window برابر باشد، آن‌ها Candidate مقایسه دقیق می‌شوند.

این روش در:

Duplicate Detection
Document Similarity
File Comparison
Text Processing

کاربرد مفهومی دارد.

کاربرد در DNA Sequence Search

Sequenceهای DNA نیز می‌توانند به صورت String نمایش داده شوند:

ACGTACGTACGT

اگر به دنبال Pattern خاصی باشیم:

TACG

می‌توان از String Matching و Rolling Hash استفاده کرد.

کاربرد در Malware و Signature Detection

فرض کنید Stream یا File بزرگی داریم و می‌خواهیم Signatureهای شناخته‌شده را بررسی کنیم.

اگر Signatureها طول مشخصی داشته باشند، Hash-based Matching می‌تواند Candidateها را سریع فیلتر کند.

ساختار مفهومی:

Data Stream
↓
Sliding Windows
↓
Rolling Hash
↓
Known Signature Hashes
↓
Verification

در سیستم‌های امنیتی واقعی، روش‌ها بسیار پیچیده‌تر هستند، اما این مدل ایده اصلی را نشان می‌دهد.

کاربرد در Data Deduplication

در Data Processing ممکن است بخواهیم Chunkهای تکراری را شناسایی کنیم.

برای مثال:

Chunk A → Hash X
Chunk B → Hash Y
Chunk C → Hash X

Chunk A و C Candidateهای Duplicate هستند.

Double Hashing چیست؟

یکی از راه‌های کاهش احتمال Collision استفاده از دو Hash مستقل است.

مثلاً:

hash1 using prime1
hash2 using prime2

دو Window فقط زمانی Candidate Match محسوب می‌شوند که:

hash1 equal
AND
hash2 equal

باشد.

به این تکنیک معمولاً Double Hashing گفته می‌شود.

احتمال Collision در این حالت به شکل قابل توجهی کاهش پیدا می‌کند.

Rolling Hash در مسائل دیگر

Rolling Hash فقط برای Rabin–Karp نیست.

این تکنیک در مسائل مختلفی دیده می‌شود:

Longest Duplicate Substring
Repeated Substring Search
String Similarity
Substring Equality Queries
Document Fingerprinting
Competitive Programming

در بسیاری از این مسائل، Hash Prefixها یا Windowهای متوالی محاسبه می‌شود.

Prefix Hash چیست؟

به جای Rolling Hash مستقیم می‌توان Hash Prefixها را از قبل محاسبه کرد.

مثلاً:

prefixHash[i]

Hash کاراکترهای ابتدای String تا موقعیت i را ذخیره می‌کند.

سپس Hash یک Substring را می‌توان با محاسبات ریاضی از دو Prefix Hash به دست آورد.

این تکنیک زمانی مفید است که تعداد زیادی Query روی یک String ثابت داشته باشیم.

سؤال رایج مصاحبه

صورت مسئله می‌تواند چنین باشد:

Pattern را در Text با استفاده از Rolling Hash پیدا کنید.

یا:

تمام Occurrenceهای Pattern را پیدا کنید.

یک پاسخ خوب باید شامل این موارد باشد:

Hash Pattern.
Hash اولین Window.
Rolling Update.
Hash Comparison.
Verification برای جلوگیری از Collision.
تحلیل Average و Worst Case.

پیدا کردن تمام Matchها

نسخه‌ای که تمام Indexها را برمی‌گرداند:

function rabinKarpAll(
  text: string,
  pattern: string
): number[] {
  const result: number[] = [];

  const n = text.length;
  const m = pattern.length;

  if (m === 0 || m > n) {
    return result;
  }

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (
      patternHash === windowHash &&
      text.slice(i, i + m) === pattern
    ) {
      result.push(i);
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return result;
}

مثلاً:

rabinKarpAll("AAAAA", "AA");

خروجی:

[0, 1, 2, 3]

اشتباهات رایج

1. اعتماد کامل به Hash

این شرط کافی نیست:

patternHash === windowHash

در نسخه‌ای که Hash Collision امکان‌پذیر است باید Verification انجام شود.

2. محاسبه Hash از صفر برای هر Window

اگر در هر موقعیت تمام Pattern را دوباره Hash کنیم، مزیت اصلی Rabin–Karp را از دست می‌دهیم.

هدف Rolling Hash این است که Update پنجره سریع باشد.

3. فراموش کردن Modulo

بدون Modulo مقادیر Hash می‌توانند بسیار بزرگ شوند و در JavaScript حتی با مسئله Precision روبه‌رو شویم.

4. انتخاب Hash ضعیف

Prime یا Base نامناسب می‌تواند Collision را افزایش دهد.

برای سیستم‌های Production باید Hash Strategy با دقت بیشتری طراحی شود.

5. اشتباه در حذف کاراکتر قدیمی

برای حذف اولین کاراکتر Window باید وزن صحیح آن را در Polynomial Hash بدانیم.

به همین دلیل highOrder را از قبل محاسبه می‌کنیم.

Edge Caseها

Pattern خالی

بسته به قرارداد می‌توان 0 یا لیست خالی برگرداند.

Pattern بزرگ‌تر از Text

Text = "abc"
Pattern = "abcdef"

هیچ Matchی وجود ندارد.

Text و Pattern برابر

algorithm
algorithm

نتیجه Index صفر است.

Matchهای هم‌پوشان

AAAAA
AA

Matchها:

0, 1, 2, 3

الگوریتم باید در صورت نیاز Overlapها را نیز در نظر بگیرد.

چه زمانی از Rabin–Karp استفاده کنیم؟

Rabin–Karp انتخاب مناسبی است وقتی:

می‌خواهیم Rolling Hash را یاد بگیریم.
تعداد زیادی Window متوالی داریم.
چند Pattern هم‌اندازه را بررسی می‌کنیم.
Hash-based filtering مفید است.
مسئله شامل Duplicate Substring یا Substring Hashing است.

اما برای یک Search ساده در Application Code معمولاً بهتر است از APIهای استاندارد زبان استفاده کنیم.

مثلاً:

text.indexOf(pattern)

یا:

text.includes(pattern)

Rabin–Karp در مصاحبه چه چیزی را می‌سنجد؟

معمولاً هدف فقط حفظ کردن کد نیست.

این الگوریتم چند مفهوم مهم را همزمان بررسی می‌کند:

Hashing
Sliding Window
Modular Arithmetic
String Matching
Collision Handling
Complexity Analysis

به همین دلیل از نظر آموزشی الگوریتم ارزشمندی است.

جمع‌بندی

Rabin–Karp الگوریتمی برای String Matching است که از Hash برای کاهش مقایسه‌های مستقیم استفاده می‌کند.

ساختار اصلی آن:

Pattern
↓
Hash

Text
↓
Sliding Window
↓
Rolling Hash
↓
Compare Hash
↓
Verify if equal

ویژگی‌های مهم:

Average Time: O(n + m)
Worst Time:   O(n × m)
Space:        O(1)

مهم‌ترین ایده‌ای که باید از Rabin–Karp به خاطر سپرد، خود String Search نیست؛ بلکه Rolling Hash است.

الگوریتم Rabin–Karp چیست؟ جستجوی سریع رشته با Rolling Hash

مسئله String Matching

Hash در Rabin–Karp چه نقشی دارد؟

Hash Collision چیست؟

Rolling Hash چیست؟

ساخت Hash به صورت عددی

Base و Prime چیستند؟

الگوریتم Rabin–Karp مرحله‌به‌مرحله

شبه‌کد Rabin–Karp

پیاده‌سازی Rabin–Karp با TypeScript

Rolling Hash چگونه Update می‌شود؟

چرا windowHash ممکن است منفی شود؟

پیچیدگی زمانی Rabin–Karp

Space Complexity

Rabin–Karp در برابر Naive Search

Rabin–Karp در برابر KMP

KMP

Rabin–Karp

چه زمانی Rabin–Karp جذاب‌تر است؟

کاربرد در Plagiarism Detection

کاربرد در Duplicate Content Detection

کاربرد در DNA Sequence Search

کاربرد در Malware و Signature Detection

کاربرد در Data Deduplication

Double Hashing چیست؟

Rolling Hash در مسائل دیگر

Prefix Hash چیست؟

سؤال رایج مصاحبه

پیدا کردن تمام Matchها

اشتباهات رایج

1. اعتماد کامل به Hash

2. محاسبه Hash از صفر برای هر Window

3. فراموش کردن Modulo

4. انتخاب Hash ضعیف

5. اشتباه در حذف کاراکتر قدیمی

Edge Caseها

Pattern خالی

Pattern بزرگ‌تر از Text

Text و Pattern برابر

Matchهای هم‌پوشان

چه زمانی از Rabin–Karp استفاده کنیم؟

Rabin–Karp در مصاحبه چه چیزی را می‌سنجد؟

جمع‌بندی

الگوریتم KMP چیست؟ جستجوی سریع رشته با Knuth–Morris–Pratt

فاصله لونشتاین (Levenshtein Distance) چیست؟ آموزش Edit Distance با Dynamic Programming

الگوریتم Rabin–Karp چیست؟ جستجوی سریع رشته با Rolling Hash

مسئله String Matching

Hash در Rabin–Karp چه نقشی دارد؟

Hash Collision چیست؟

Rolling Hash چیست؟

ساخت Hash به صورت عددی

Base و Prime چیستند؟

الگوریتم Rabin–Karp مرحله‌به‌مرحله

شبه‌کد Rabin–Karp

پیاده‌سازی Rabin–Karp با TypeScript

Rolling Hash چگونه Update می‌شود؟

چرا windowHash ممکن است منفی شود؟

پیچیدگی زمانی Rabin–Karp

Space Complexity

Rabin–Karp در برابر Naive Search

Rabin–Karp در برابر KMP

KMP

Rabin–Karp

چه زمانی Rabin–Karp جذاب‌تر است؟

کاربرد در Plagiarism Detection

کاربرد در Duplicate Content Detection

کاربرد در DNA Sequence Search

کاربرد در Malware و Signature Detection

کاربرد در Data Deduplication

Double Hashing چیست؟

Rolling Hash در مسائل دیگر

Prefix Hash چیست؟

سؤال رایج مصاحبه

پیدا کردن تمام Matchها

اشتباهات رایج

1. اعتماد کامل به Hash

2. محاسبه Hash از صفر برای هر Window

3. فراموش کردن Modulo

4. انتخاب Hash ضعیف

5. اشتباه در حذف کاراکتر قدیمی