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

الگوریتم Knuth–Morris–Pratt که معمولاً با نام KMP شناخته می‌شود، یکی از الگوریتم‌های کلاسیک و مهم برای پیدا کردن یک Pattern داخل یک Text است.

فرض کنید می‌خواهیم مشخص کنیم رشته زیر:

ABABCABAB

آیا شامل الگوی زیر هست یا خیر:

ABAB

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

KMP دقیقاً برای حل همین مشکل طراحی شده است.

ایده اصلی آن این است:

وقتی بخشی از Pattern قبلاً با Text تطابق داشته است، نباید تمام اطلاعات آن تطابق را پس از اولین mismatch دور بریزیم.

KMP با استفاده از یک آرایه کمکی به نام LPS مشخص می‌کند پس از mismatch، Pattern را تا کجا می‌توان جابه‌جا کرد بدون اینکه مقایسه‌های قبلی دوباره انجام شوند.

مشکل جستجوی ساده رشته

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

Text:    A B A B A B C
Pattern: A B A B C

ابتدا چند کاراکتر تطابق دارند:

A B A B
A B A B

اما سپس داریم:

Text:    A
Pattern: C

و mismatch رخ می‌دهد.

در الگوریتم ساده ممکن است Pattern را فقط یک موقعیت جلو ببریم و دوباره اطلاعاتی را مقایسه کنیم که قبلاً درباره آن‌ها می‌دانستیم.

KMP متوجه می‌شود بخشی از Pattern که قبلاً match شده، خودش دارای ساختار تکراری است و می‌توان از این اطلاعات استفاده کرد.

Prefix و Suffix چیست؟

برای درک KMP ابتدا باید Prefix و Suffix را بشناسیم.

برای رشته:

ABAB

Prefixهای Proper آن عبارت‌اند از:

A
AB
ABA

Suffixهای Proper:

B
AB
BAB

کلمه Proper یعنی خود رشته کامل در نظر گرفته نمی‌شود.

بزرگ‌ترین Prefix که همزمان Suffix هم باشد:

AB

طول آن برابر 2 است.

این مفهوم اساس آرایه LPS است.

LPS چیست؟

LPS مخفف:

Longest Proper Prefix which is also a Suffix

است.

برای هر موقعیت از Pattern مشخص می‌کنیم طول بلندترین Prefix مناسب که در همان substring به عنوان Suffix نیز ظاهر شده چقدر است.

Pattern زیر را در نظر بگیرید:

A B A B A C

آرایه LPS آن:

Pattern: A B A B A C
Index:   0 1 2 3 4 5
LPS:     0 0 1 2 3 0

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

برای:

ABA

Prefix:

و Suffix:

پس:

LPS[2] = 1

برای:

ABAB

بزرگ‌ترین Prefix/Suffix مشترک:

AB

پس:

LPS[3] = 2

برای:

ABABA

بزرگ‌ترین Prefix/Suffix:

ABA

پس:

LPS[4] = 3

چرا LPS مهم است؟

فرض کنید در حال مقایسه Pattern هستیم و چند کاراکتر اول آن قبلاً Match شده‌اند.

اگر mismatch رخ دهد، KMP به جای بازگشت به ابتدای Pattern می‌گوید:

j = LPS[j - 1]

یعنی بخشی از Pattern که می‌دانیم می‌تواند هنوز معتبر باشد حفظ می‌شود.

این همان چیزی است که از مقایسه مجدد جلوگیری می‌کند.

مثال مرحله‌به‌مرحله

Text:

ABABDABACDABABCABAB

Pattern:

ABABCABAB

LPS Pattern برابر است با:

Pattern: A B A B C A B A B
LPS:     0 0 1 2 0 1 2 3 4

KMP با دو Pointer کار می‌کند:

i → Text
j → Pattern

اگر:

text[i] == pattern[j]

باشد:

i++
j++

اگر j == pattern.length شود، Pattern پیدا شده است.

اما اگر mismatch رخ دهد و j > 0 باشد:

j = lps[j - 1]

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

همین ویژگی دلیل اصلی کارایی KMP است.

ساخت آرایه LPS

ابتدا باید LPS را بسازیم.

شبه‌کد:

lps[0] = 0
length = 0
i = 1

while i < pattern.length:
    if pattern[i] == pattern[length]:
        length++
        lps[i] = length
        i++
    else:
        if length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i++

نکته مهم این است که حتی هنگام ساخت LPS نیز از اطلاعات محاسبه‌شده قبلی استفاده می‌کنیم.

پیاده‌سازی LPS با TypeScript

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);

  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length !== 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

برای مثال:

console.log(buildLPS("ABABCABAB"));

خروجی:

[0, 0, 1, 2, 0, 1, 2, 3, 4]

پیاده‌سازی کامل KMP با TypeScript

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);

  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length !== 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) {
    return 0;
  }

  const lps = buildLPS(pattern);

  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        return i - j;
      }
    } else if (j !== 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }

  return -1;
}

console.log(
  kmpSearch("ABABDABACDABABCABAB", "ABABCABAB")
);

خروجی:

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

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

گاهی فقط اولین occurrence کافی نیست و می‌خواهیم تمام موقعیت‌هایی را پیدا کنیم که Pattern ظاهر شده است.

function kmpSearchAll(text: string, pattern: string): number[] {
  if (pattern.length === 0) {
    return [];
  }

  const lps = buildLPS(pattern);
  const result: number[] = [];

  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        result.push(i - j);
        j = lps[j - 1];
      }
    } else if (j !== 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }

  return result;
}

مثلاً:

kmpSearchAll("AAAAA", "AA");

می‌تواند Matchهای هم‌پوشان را نیز پیدا کند:

[0, 1, 2, 3]

پیچیدگی زمانی KMP

اگر طول Text برابر n و طول Pattern برابر m باشد:

ساخت LPS:

O(m)

جستجو:

O(n)

در نتیجه کل الگوریتم:

Time Complexity: O(n + m)
Space Complexity: O(m)

فضای O(m) برای نگهداری آرایه LPS استفاده می‌شود.

چرا KMP واقعاً O(n) است؟

ممکن است در نگاه اول به دلیل تغییر Pointer مربوط به Pattern تصور کنیم بعضی کاراکترها چند بار بررسی می‌شوند.

اما Pointer مربوط به Text یعنی i هرگز به عقب حرکت نمی‌کند.

KMP با استفاده از LPS مشخص می‌کند Pattern را چگونه جابه‌جا کند و به همین دلیل از شروع دوباره مقایسه از موقعیت‌های قبلی Text جلوگیری می‌شود.

این ویژگی باعث می‌شود مرحله Search زمان خطی داشته باشد.

Naive Search در برابر KMP

در روش ساده یا Naive String Matching، در بدترین حالت ممکن است برای هر موقعیت Text تقریباً کل Pattern بررسی شود.

پیچیدگی بدترین حالت:

O(n × m)

اما KMP:

O(n + m)

برای Textهای کوچک، تفاوت ممکن است محسوس نباشد. اما در داده‌های بزرگ یا Patternهای دارای ساختار تکراری، KMP مزیت مهمی دارد.

یک مثال بد برای Naive Search

فرض کنید:

Text:
AAAAAAAAAAAAAAAAAB

Pattern:
AAAAAB

الگوریتم ساده بارها تعداد زیادی A را دوباره مقایسه می‌کند.

اما KMP از ساختار تکراری AAAAA استفاده می‌کند و با کمک LPS از بسیاری از این مقایسه‌ها جلوگیری می‌کند.

کاربردهای واقعی KMP

1. جستجوی متن

یکی از واضح‌ترین کاربردها پیدا کردن Pattern در فایل، Document، Log یا Text بزرگ است.

2. پردازش DNA

Sequenceهای DNA را می‌توان مانند رشته‌ها در نظر گرفت و Patternهای خاصی را در آن‌ها جستجو کرد.

3. سیستم‌های Log Analysis

برای پیدا کردن Signature یا Pattern مشخص در Logهای بزرگ می‌توان از الگوریتم‌های جستجوی رشته استفاده کرد.

4. Data Processing

در Pipelineهای پردازش متن، ممکن است نیاز باشد یک Token Sequence یا Pattern مشخص بارها جستجو شود.

5. Intrusion Detection

برخی سیستم‌های امنیتی نیاز دارند Signatureهای مشخصی را در Streamهای داده پیدا کنند. String Matching یکی از اجزای چنین سیستم‌هایی است.

6. Text Editors و Search Engines

مفاهیم String Matching در قابلیت‌هایی مانند Find و Search اهمیت دارند، هرچند نرم‌افزارهای واقعی بسته به نیاز ممکن است الگوریتم‌های دیگری نیز استفاده کنند.

کاربرد KMP در مصاحبه‌های برنامه‌نویسی

KMP یکی از الگوریتم‌هایی است که بیشتر از آنکه صرفاً حفظ کد آن مهم باشد، درک منطق LPS اهمیت دارد.

سؤال‌های رایج می‌توانند شامل موارد زیر باشند:

Find substring in string
Find all pattern occurrences
Build LPS array
Detect repeated substring pattern
Longest prefix that is also suffix
Pattern matching in streaming data

اگر بتوانید دلیل استفاده از LPS را توضیح دهید، بخش اصلی الگوریتم را درک کرده‌اید.

سؤال مهم: چرا بعد از mismatch از LPS[j - 1] استفاده می‌کنیم؟

فرض کنید j کاراکتر از Pattern قبلاً Match شده‌اند.

یعنی:

pattern[0 ... j-1]

با بخشی از Text تطابق دارد.

اگر در موقعیت j mismatch رخ دهد، می‌خواهیم بدانیم بزرگ‌ترین بخشی از این Pattern که می‌تواند همچنان Match باقی بماند چیست.

این دقیقاً همان اطلاعاتی است که در:

LPS[j - 1]

ذخیره شده است.

پس به جای:

j = 0

می‌گوییم:

j = LPS[j - 1]

و اطلاعات Match قبلی را حفظ می‌کنیم.

اشتباه رایج هنگام پیاده‌سازی KMP

یکی از رایج‌ترین اشتباهات این است که هنگام mismatch هم i و هم j را تغییر دهیم.

اگر:

j > 0

باشد، نباید i افزایش پیدا کند.

فقط داریم:

j = lps[j - 1];

زیرا همان کاراکتر Text باید دوباره با موقعیت جدید Pattern مقایسه شود.

Edge Caseها

هنگام پیاده‌سازی بهتر است موارد زیر را در نظر بگیرید:

Pattern خالی

text = "hello"
pattern = ""

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

Pattern بزرگ‌تر از Text

text = "abc"
pattern = "abcdef"

نتیجه طبیعی:

-1

Pattern برابر Text

text = "algorithm"
pattern = "algorithm"

نتیجه:

Pattern تکراری

text = "AAAAA"
pattern = "AAA"

این نوع داده برای درک اهمیت LPS بسیار مناسب است.

آیا همیشه باید از KMP استفاده کنیم؟

خیر.

در کدهای روزمره معمولاً توابع داخلی زبان مانند:

text.indexOf(pattern)

یا:

text.includes(pattern)

انتخاب مناسب‌تری هستند.

هدف یادگیری KMP این نیست که تمام عملیات Search نرم‌افزار را دستی بازنویسی کنیم.

KMP زمانی اهمیت پیدا می‌کند که:

بخواهیم String Matching را عمیقاً درک کنیم.
تضمین زمانی O(n + m) مهم باشد.
با حجم زیادی از متن کار کنیم.
مسئله الگوریتمی خاصی بر پایه Prefix/Suffix داشته باشیم.
در مصاحبه یا Competitive Programming با Pattern Matching روبه‌رو شویم.

جمع‌بندی

الگوریتم Knuth–Morris–Pratt یک روش هوشمند برای جستجوی Pattern داخل Text است که مهم‌ترین ویژگی آن جلوگیری از مقایسه‌های تکراری است.

KMP این کار را با پیش‌پردازش Pattern و ساخت آرایه LPS انجام می‌دهد.

مهم‌ترین نکات آن عبارت‌اند از:

Preprocessing Pattern → LPS
Searching Text        → No backward movement of i
Time Complexity       → O(n + m)
Space Complexity      → O(m)

اگر فقط یک نکته از KMP به خاطر بسپاریم، بهتر است این باشد:

وقتی mismatch رخ می‌دهد، لازم نیست همه اطلاعات Match قبلی را دور بریزیم؛ LPS به ما می‌گوید چه بخشی از Pattern هنوز قابل استفاده است.

همین ایده ساده KMP را از یک جستجوی معمولی به یکی از الگوریتم‌های کلاسیک و مهم String Matching تبدیل کرده است.

فرض کنید می‌خواهیم مشخص کنیم رشته زیر:

ABABCABAB

آیا شامل الگوی زیر هست یا خیر:

ABAB

KMP دقیقاً برای حل همین مشکل طراحی شده است.

ایده اصلی آن این است:

وقتی بخشی از Pattern قبلاً با Text تطابق داشته است، نباید تمام اطلاعات آن تطابق را پس از اولین mismatch دور بریزیم.

مشکل جستجوی ساده رشته

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

Text:    A B A B A B C
Pattern: A B A B C

ابتدا چند کاراکتر تطابق دارند:

A B A B
A B A B

اما سپس داریم:

Text:    A
Pattern: C

و mismatch رخ می‌دهد.

Prefix و Suffix چیست؟

برای درک KMP ابتدا باید Prefix و Suffix را بشناسیم.

برای رشته:

ABAB

Prefixهای Proper آن عبارت‌اند از:

A
AB
ABA

Suffixهای Proper:

B
AB
BAB

کلمه Proper یعنی خود رشته کامل در نظر گرفته نمی‌شود.

بزرگ‌ترین Prefix که همزمان Suffix هم باشد:

AB

طول آن برابر 2 است.

این مفهوم اساس آرایه LPS است.

LPS چیست؟

LPS مخفف:

Longest Proper Prefix which is also a Suffix

است.

برای هر موقعیت از Pattern مشخص می‌کنیم طول بلندترین Prefix مناسب که در همان substring به عنوان Suffix نیز ظاهر شده چقدر است.

Pattern زیر را در نظر بگیرید:

A B A B A C

آرایه LPS آن:

Pattern: A B A B A C
Index:   0 1 2 3 4 5
LPS:     0 0 1 2 3 0

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

برای:

ABA

Prefix:

و Suffix:

پس:

LPS[2] = 1

برای:

ABAB

بزرگ‌ترین Prefix/Suffix مشترک:

AB

پس:

LPS[3] = 2

برای:

ABABA

بزرگ‌ترین Prefix/Suffix:

ABA

پس:

LPS[4] = 3

چرا LPS مهم است؟

فرض کنید در حال مقایسه Pattern هستیم و چند کاراکتر اول آن قبلاً Match شده‌اند.

اگر mismatch رخ دهد، KMP به جای بازگشت به ابتدای Pattern می‌گوید:

j = LPS[j - 1]

یعنی بخشی از Pattern که می‌دانیم می‌تواند هنوز معتبر باشد حفظ می‌شود.

این همان چیزی است که از مقایسه مجدد جلوگیری می‌کند.

مثال مرحله‌به‌مرحله

Text:

ABABDABACDABABCABAB

Pattern:

ABABCABAB

LPS Pattern برابر است با:

Pattern: A B A B C A B A B
LPS:     0 0 1 2 0 1 2 3 4

KMP با دو Pointer کار می‌کند:

i → Text
j → Pattern

اگر:

text[i] == pattern[j]

باشد:

i++
j++

اگر j == pattern.length شود، Pattern پیدا شده است.

اما اگر mismatch رخ دهد و j > 0 باشد:

j = lps[j - 1]

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

همین ویژگی دلیل اصلی کارایی KMP است.

ساخت آرایه LPS

ابتدا باید LPS را بسازیم.

شبه‌کد:

lps[0] = 0
length = 0
i = 1

while i < pattern.length:
    if pattern[i] == pattern[length]:
        length++
        lps[i] = length
        i++
    else:
        if length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i++

نکته مهم این است که حتی هنگام ساخت LPS نیز از اطلاعات محاسبه‌شده قبلی استفاده می‌کنیم.

پیاده‌سازی LPS با TypeScript

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);

  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length !== 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

برای مثال:

console.log(buildLPS("ABABCABAB"));

خروجی:

[0, 0, 1, 2, 0, 1, 2, 3, 4]

پیاده‌سازی کامل KMP با TypeScript

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);

  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length !== 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) {
    return 0;
  }

  const lps = buildLPS(pattern);

  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        return i - j;
      }
    } else if (j !== 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }

  return -1;
}

console.log(
  kmpSearch("ABABDABACDABABCABAB", "ABABCABAB")
);

خروجی:

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

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

گاهی فقط اولین occurrence کافی نیست و می‌خواهیم تمام موقعیت‌هایی را پیدا کنیم که Pattern ظاهر شده است.

function kmpSearchAll(text: string, pattern: string): number[] {
  if (pattern.length === 0) {
    return [];
  }

  const lps = buildLPS(pattern);
  const result: number[] = [];

  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        result.push(i - j);
        j = lps[j - 1];
      }
    } else if (j !== 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }

  return result;
}

مثلاً:

kmpSearchAll("AAAAA", "AA");

می‌تواند Matchهای هم‌پوشان را نیز پیدا کند:

[0, 1, 2, 3]

پیچیدگی زمانی KMP

اگر طول Text برابر n و طول Pattern برابر m باشد:

ساخت LPS:

O(m)

جستجو:

O(n)

در نتیجه کل الگوریتم:

Time Complexity: O(n + m)
Space Complexity: O(m)

فضای O(m) برای نگهداری آرایه LPS استفاده می‌شود.

چرا KMP واقعاً O(n) است؟

ممکن است در نگاه اول به دلیل تغییر Pointer مربوط به Pattern تصور کنیم بعضی کاراکترها چند بار بررسی می‌شوند.

اما Pointer مربوط به Text یعنی i هرگز به عقب حرکت نمی‌کند.

این ویژگی باعث می‌شود مرحله Search زمان خطی داشته باشد.

Naive Search در برابر KMP

در روش ساده یا Naive String Matching، در بدترین حالت ممکن است برای هر موقعیت Text تقریباً کل Pattern بررسی شود.

پیچیدگی بدترین حالت:

O(n × m)

اما KMP:

O(n + m)

یک مثال بد برای Naive Search

فرض کنید:

Text:
AAAAAAAAAAAAAAAAAB

Pattern:
AAAAAB

الگوریتم ساده بارها تعداد زیادی A را دوباره مقایسه می‌کند.

اما KMP از ساختار تکراری AAAAA استفاده می‌کند و با کمک LPS از بسیاری از این مقایسه‌ها جلوگیری می‌کند.

کاربردهای واقعی KMP

1. جستجوی متن

یکی از واضح‌ترین کاربردها پیدا کردن Pattern در فایل، Document، Log یا Text بزرگ است.

2. پردازش DNA

Sequenceهای DNA را می‌توان مانند رشته‌ها در نظر گرفت و Patternهای خاصی را در آن‌ها جستجو کرد.

3. سیستم‌های Log Analysis

برای پیدا کردن Signature یا Pattern مشخص در Logهای بزرگ می‌توان از الگوریتم‌های جستجوی رشته استفاده کرد.

4. Data Processing

در Pipelineهای پردازش متن، ممکن است نیاز باشد یک Token Sequence یا Pattern مشخص بارها جستجو شود.

5. Intrusion Detection

6. Text Editors و Search Engines

کاربرد KMP در مصاحبه‌های برنامه‌نویسی

KMP یکی از الگوریتم‌هایی است که بیشتر از آنکه صرفاً حفظ کد آن مهم باشد، درک منطق LPS اهمیت دارد.

سؤال‌های رایج می‌توانند شامل موارد زیر باشند:

Find substring in string
Find all pattern occurrences
Build LPS array
Detect repeated substring pattern
Longest prefix that is also suffix
Pattern matching in streaming data

اگر بتوانید دلیل استفاده از LPS را توضیح دهید، بخش اصلی الگوریتم را درک کرده‌اید.

سؤال مهم: چرا بعد از mismatch از LPS[j - 1] استفاده می‌کنیم؟

فرض کنید j کاراکتر از Pattern قبلاً Match شده‌اند.

یعنی:

pattern[0 ... j-1]

با بخشی از Text تطابق دارد.

این دقیقاً همان اطلاعاتی است که در:

LPS[j - 1]

ذخیره شده است.

پس به جای:

j = 0

می‌گوییم:

j = LPS[j - 1]

و اطلاعات Match قبلی را حفظ می‌کنیم.

اشتباه رایج هنگام پیاده‌سازی KMP

یکی از رایج‌ترین اشتباهات این است که هنگام mismatch هم i و هم j را تغییر دهیم.

اگر:

j > 0

باشد، نباید i افزایش پیدا کند.

فقط داریم:

j = lps[j - 1];

زیرا همان کاراکتر Text باید دوباره با موقعیت جدید Pattern مقایسه شود.

Edge Caseها

هنگام پیاده‌سازی بهتر است موارد زیر را در نظر بگیرید:

Pattern خالی

text = "hello"
pattern = ""

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

Pattern بزرگ‌تر از Text

text = "abc"
pattern = "abcdef"

نتیجه طبیعی:

-1

Pattern برابر Text

text = "algorithm"
pattern = "algorithm"

نتیجه:

Pattern تکراری

text = "AAAAA"
pattern = "AAA"

این نوع داده برای درک اهمیت LPS بسیار مناسب است.

آیا همیشه باید از KMP استفاده کنیم؟

خیر.

در کدهای روزمره معمولاً توابع داخلی زبان مانند:

text.indexOf(pattern)

یا:

text.includes(pattern)

انتخاب مناسب‌تری هستند.

هدف یادگیری KMP این نیست که تمام عملیات Search نرم‌افزار را دستی بازنویسی کنیم.

KMP زمانی اهمیت پیدا می‌کند که:

بخواهیم String Matching را عمیقاً درک کنیم.
تضمین زمانی O(n + m) مهم باشد.
با حجم زیادی از متن کار کنیم.
مسئله الگوریتمی خاصی بر پایه Prefix/Suffix داشته باشیم.
در مصاحبه یا Competitive Programming با Pattern Matching روبه‌رو شویم.

جمع‌بندی

KMP این کار را با پیش‌پردازش Pattern و ساخت آرایه LPS انجام می‌دهد.

مهم‌ترین نکات آن عبارت‌اند از:

Preprocessing Pattern → LPS
Searching Text        → No backward movement of i
Time Complexity       → O(n + m)
Space Complexity      → O(m)

اگر فقط یک نکته از KMP به خاطر بسپاریم، بهتر است این باشد:

وقتی mismatch رخ می‌دهد، لازم نیست همه اطلاعات Match قبلی را دور بریزیم؛ LPS به ما می‌گوید چه بخشی از Pattern هنوز قابل استفاده است.

همین ایده ساده KMP را از یک جستجوی معمولی به یکی از الگوریتم‌های کلاسیک و مهم String Matching تبدیل کرده است.

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

مشکل جستجوی ساده رشته

Prefix و Suffix چیست؟

LPS چیست؟

چرا LPS مهم است؟

مثال مرحله‌به‌مرحله

ساخت آرایه LPS

پیاده‌سازی LPS با TypeScript

پیاده‌سازی کامل KMP با TypeScript

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

پیچیدگی زمانی KMP

چرا KMP واقعاً O(n) است؟

Naive Search در برابر KMP

یک مثال بد برای Naive Search

کاربردهای واقعی KMP

1. جستجوی متن

2. پردازش DNA

3. سیستم‌های Log Analysis

4. Data Processing

5. Intrusion Detection

6. Text Editors و Search Engines

کاربرد KMP در مصاحبه‌های برنامه‌نویسی

سؤال مهم: چرا بعد از mismatch از LPS[j - 1] استفاده می‌کنیم؟

اشتباه رایج هنگام پیاده‌سازی KMP

Edge Caseها

Pattern خالی

Pattern بزرگ‌تر از Text

Pattern برابر Text

Pattern تکراری

آیا همیشه باید از KMP استفاده کنیم؟

جمع‌بندی

فاصله همینگ (Hamming Distance) چیست؟ از مفهوم تا پیاده‌سازی و کاربردهای واقعی

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

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

مشکل جستجوی ساده رشته

Prefix و Suffix چیست؟

LPS چیست؟

چرا LPS مهم است؟

مثال مرحله‌به‌مرحله

ساخت آرایه LPS

پیاده‌سازی LPS با TypeScript

پیاده‌سازی کامل KMP با TypeScript

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

پیچیدگی زمانی KMP

چرا KMP واقعاً O(n) است؟

Naive Search در برابر KMP

یک مثال بد برای Naive Search

کاربردهای واقعی KMP

1. جستجوی متن

2. پردازش DNA

3. سیستم‌های Log Analysis

4. Data Processing

5. Intrusion Detection

6. Text Editors و Search Engines

کاربرد KMP در مصاحبه‌های برنامه‌نویسی

سؤال مهم: چرا بعد از mismatch از LPS[j - 1] استفاده می‌کنیم؟

اشتباه رایج هنگام پیاده‌سازی KMP

Edge Caseها

Pattern خالی

Pattern بزرگ‌تر از Text

Pattern برابر Text

Pattern تکراری

آیا همیشه باید از KMP استفاده کنیم؟

جمع‌بندی

فاصله همینگ (Hamming Distance) چیست؟ از مفهوم تا پیاده‌سازی و کاربردهای واقعی

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