KMP Pattern Matching Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does KMP stand for in the KMP Pattern Matching Algorithm?

KMP stands for Knuth-Morris-Pratt, the last names of the three computer scientists who developed this efficient pattern matching algorithm.

beginner

What is the main advantage of the KMP algorithm over the naive pattern matching approach?

KMP avoids rechecking characters that have already been matched by using a precomputed table, making it faster especially for large texts and patterns.

intermediate

What is the purpose of the 'Longest Prefix Suffix' (LPS) array in KMP?

The LPS array stores the length of the longest proper prefix of the pattern that is also a suffix for each prefix of the pattern. It helps decide where to continue matching after a mismatch.

intermediate

In KMP, what happens when a mismatch occurs after some characters have matched?

Instead of restarting from the next character in the text, KMP uses the LPS array to shift the pattern to the right position, skipping unnecessary comparisons.

intermediate

What is the time complexity of the KMP Pattern Matching Algorithm?

The time complexity is O(n + m), where n is the length of the text and m is the length of the pattern, because each character is processed at most twice.

What does the LPS array in KMP represent?

A Length of the pattern

B Positions of matches in the text

C Longest prefix which is also suffix for pattern prefixes

D Number of mismatches found

The LPS array stores the longest proper prefix which is also a suffix for each prefix of the pattern.

When a mismatch occurs in KMP, what does the algorithm do?

A Uses the LPS array to shift the pattern without rechecking matched characters

B Restarts matching from the next character in the text

C Stops the search immediately

D Skips the entire pattern and moves forward

KMP uses the LPS array to avoid rechecking matched characters and shifts the pattern efficiently.

What is the worst-case time complexity of KMP?

A O(n + m)

B O(n^2)

C O(n * m)

D O(m^2)

KMP runs in linear time relative to the sum of text and pattern lengths, O(n + m).

Which of these is NOT a step in the KMP algorithm?

A Compare characters of text and pattern

B Restart matching from the beginning of the text on mismatch

C Precompute the LPS array

D Shift pattern using LPS on mismatch

KMP does NOT restart from the beginning of the text on mismatch; it uses the LPS array to shift the pattern.

Why is KMP more efficient than naive pattern matching?

A It uses recursion

B It only works on small texts

C It checks every character multiple times

D It skips unnecessary comparisons using the LPS array

KMP uses the LPS array to skip unnecessary comparisons, making it more efficient.

Explain how the LPS array is constructed and how it helps in the KMP algorithm.

Think about prefixes and suffixes in the pattern and how they guide the search after mismatches.

Describe the step-by-step process of searching a pattern in a text using the KMP algorithm.

Start from building the LPS array, then explain how matching and shifting happen.

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) pattern matching algorithm?

easy

A. To sort an array of numbers in ascending order

B. To find occurrences of a pattern string within a text efficiently

C. To reverse a string in linear time

D. To calculate the factorial of a number recursively

Solution

1. Step 1: Understand the problem KMP solves

   KMP is designed to find all occurrences of a pattern inside a text without rechecking characters unnecessarily.

2. Step 2: Compare with other options

   Sorting, reversing strings, and factorial calculation are unrelated to pattern searching.

3. Final Answer:

   To find occurrences of a pattern string within a text efficiently -> Option B

4. Quick Check:

   KMP = Pattern searching [OK]

Hint: KMP is about searching patterns fast in text [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP calculates factorials

2. Which of the following is the correct way to initialize the prefix array (lps) in the KMP algorithm in JavaScript?

easy

A. const lps = new Array(pattern.length).fill(null);

B. const lps = Array(pattern.length);

C. const lps = []; lps.length = pattern.length;

D. const lps = new Array(pattern.length).fill(0);

Solution

1. Step 1: Understand prefix array initialization

   The prefix array (lps) must be initialized with zeros to store lengths of longest prefix suffix.

2. Step 2: Check each option

   const lps = new Array(pattern.length).fill(0); correctly creates an array of the pattern's length filled with zeros. const lps = Array(pattern.length); creates an array but leaves elements undefined. const lps = []; lps.length = pattern.length; sets length but elements are undefined. const lps = new Array(pattern.length).fill(null); fills with null, which is incorrect.

3. Final Answer:

   const lps = new Array(pattern.length).fill(0); -> Option D

4. Quick Check:

   Prefix array = zeros [OK]

Hint: Prefix array must start with zeros for correct matching [OK]

Common Mistakes:

• Leaving prefix array elements undefined
• Filling prefix array with null instead of zero
• Not initializing prefix array length

3. What will be the output of the following JavaScript code snippet using KMP to find pattern 'ABABC' in text 'ABABABCABABCBC'?

function KMPSearch(pattern, text) {
  const lps = computeLPSArray(pattern);
  let i = 0, j = 0;
  const result = [];
  while (i < text.length) {
    if (pattern[j] === text[i]) {
      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;
}

function computeLPSArray(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let 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++;
    }
  }
  return lps;
}

console.log(KMPSearch('ABABC', 'ABABABCABABCBC'));

medium

A. [1, 6]

B. [0, 5]

C. [2, 7]

D. [3, 8]

Solution

1. Step 1: Compute LPS array for pattern 'ABABC'

   LPS array is [0, 0, 1, 2, 0]. This helps skip characters on mismatch.

2. Step 2: Trace pattern matches in text 'ABABABCABABCBC'

   Pattern matches start at index 2 and again at index 7 in the text.

3. Final Answer:

   [2, 7] -> Option C

4. Quick Check:

   Match indices = [2, 7] [OK]

Hint: Use LPS to jump and find pattern start indices [OK]

Common Mistakes:

• Incorrect LPS array calculation
• Off-by-one errors in indices
• Confusing pattern length with text length

4. Identify the bug in this KMP prefix array computation code snippet:

function computeLPSArray(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 0;
  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;
}

medium

A. The loop should start with i = 1, not i = 0

B. The length variable should be initialized to 1

C. The lps array should be filled with -1 instead of 0

D. The condition pattern[i] === pattern[length] should be reversed

Solution

1. Step 1: Check loop initialization

   The prefix array computation starts from index 1 because index 0 always has lps value 0.

2. Step 2: Identify impact of starting at i=0

   Starting at i=0 causes comparing pattern[0] with pattern[0] unnecessarily and overwrites lps[0], which should remain 0.

3. Final Answer:

   The loop should start with i = 1, not i = 0 -> Option A

4. Quick Check:

   Start loop at 1 for prefix array [OK]

Hint: Prefix array loop always starts at 1 [OK]

Common Mistakes:

• Starting loop at 0
• Initializing length incorrectly
• Filling lps with wrong values

5. Given a large text and a pattern, how can you modify the KMP algorithm to count overlapping occurrences of the pattern in the text? For example, pattern 'AAA' in text 'AAAAA' occurs 3 times (positions 0,1,2). Which change is correct?

hard

A. After a match, set j = lps[j - 1] instead of resetting j to 0

B. After a match, increment i by pattern length to skip matched part

C. After a match, reset both i and j to 0 to restart search

D. After a match, increment j by 1 to continue matching

Solution

1. Step 1: Understand overlapping matches

   Overlapping matches require continuing search from the longest proper prefix which is also suffix, not restarting.

2. Step 2: Apply correct jump after match

   Setting j = lps[j - 1] after a match allows the algorithm to find overlapping occurrences without missing any.

3. Final Answer:

   After a match, set j = lps[j - 1] instead of resetting j to 0 -> Option A

4. Quick Check:

   Use lps jump to count overlaps [OK]

Hint: Use lps jump after match to find overlaps [OK]

Common Mistakes:

• Resetting j to 0 after match
• Skipping characters by incrementing i too much
• Not handling overlaps correctly