KMP Pattern Matching Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prefix table computation

What is the output of the prefix table (lps array) after running the KMP preprocessing on the pattern "ABABCABAB"?

DSA Javascript

function computeLPSArray(pattern) {
  const lps = 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(computeLPSArray("ABABCABAB"));

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

B [0, 1, 0, 1, 2, 3, 4, 5, 6]

C [0, 0, 0, 1, 2, 0, 1, 2, 3]

D [0, 1, 1, 2, 3, 0, 1, 2, 3]

💡 Hint

Remember the prefix table stores the length of the longest proper prefix which is also suffix for each substring.

The prefix table (lps array) for pattern "ABABCABAB" is [0, 0, 1, 2, 0, 1, 2, 3, 4]. This array helps KMP skip unnecessary comparisons.

❓ Predict Output

intermediate

KMP search output for a given text and pattern

What is the output (starting indices) of the KMP search for pattern "ABAB" in text "ABABDABABABC"?

DSA Javascript

function KMPSearch(pattern, text) {
  const lps = Array(pattern.length).fill(0);
  let j = 0;
  const result = [];

  function computeLPSArray(pattern) {
    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++;
        }
      }
    }
  }

  computeLPSArray(pattern);

  let i = 0;
  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 (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  return result;
}

console.log(KMPSearch("ABAB", "ABABDABABABC"));

A [0, 5]

B [1, 5]

C [0, 5, 7]

D [2, 6]

💡 Hint

Look for exact matches of the pattern in the text and note their starting indices.

The pattern "ABAB" appears starting at indices 0, 5, and 7 in the text "ABABDABABABC".

🧠 Conceptual

advanced

Understanding the role of the LPS array in KMP

Which of the following best describes the role of the LPS (Longest Prefix Suffix) array in the KMP algorithm?

A It stores the indices of all occurrences of the pattern in the text.

B It stores the length of the longest prefix which is also a suffix for each prefix of the pattern to avoid rechecking characters.

C It counts the total number of mismatches during the search process.

D It holds the reversed pattern to compare with the text from the end.

💡 Hint

Think about how KMP avoids rechecking characters after a mismatch.

The LPS array helps KMP skip unnecessary comparisons by storing the longest prefix which is also suffix for each prefix of the pattern.

❓ Predict Output

advanced

Output of KMP search with overlapping patterns

What is the output of the KMP search for pattern "AAA" in text "AAAAAA"?

DSA Javascript

function KMPSearch(pattern, text) {
  const lps = Array(pattern.length).fill(0);
  let j = 0;
  const result = [];

  function computeLPSArray(pattern) {
    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++;
        }
      }
    }
  }

  computeLPSArray(pattern);

  let i = 0;
  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 (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  return result;
}

console.log(KMPSearch("AAA", "AAAAAA"));

A [0, 1, 2, 3]

B [0, 3]

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

D [1, 2, 3]

💡 Hint

Consider overlapping occurrences of the pattern in the text.

The pattern "AAA" appears starting at indices 0, 1, 2, and 3 in the text "AAAAAA" due to overlapping matches.

🧠 Conceptual

expert

Time complexity of KMP algorithm

What is the worst-case time complexity of the KMP pattern matching algorithm and why?

A O(n^2), because it uses nested loops for matching and preprocessing.

B O(n * m), because it compares each character of the pattern with every character of the text.

C O(m log n), because it uses binary search on the pattern during matching.

D O(n + m), because it processes each character of the text and pattern at most once using the LPS array.

💡 Hint

Consider how the LPS array helps avoid rechecking characters.

KMP runs in O(n + m) time because it uses the LPS array to skip unnecessary comparisons, ensuring each character is processed at most once.

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