KMP Pattern Matching Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the LPS array with zeros.

DSA Javascript

const lps = new Array(pattern.length).fill([1]);

Drag options to blanks, or click blank then click option'

A-1

B1

C0

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing LPS with ones or negative numbers.

Leaving LPS uninitialized.

The LPS (Longest Prefix Suffix) array should be initialized with zeros to start computing prefix lengths.

2fill in blank

medium

Complete the while loop condition to compute the LPS array correctly.

DSA Javascript

while (len > 0 && pattern[len] !== pattern[[1]]) { len = lps[len - 1]; }

Drag options to blanks, or click blank then click option'

Aj

Bpos

Cindex

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined variables like 'j' or 'pos'.

Confusing the index variables.

The variable 'i' is used as the current index in the pattern while computing LPS.

3fill in blank

hard

Fix the error in the KMP search loop condition to avoid infinite loops.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A1

B0

Cj - 1

Dlps[j]

Attempts:

3 left

💡 Hint

Common Mistakes

Setting j to 1 or lps[j], causing incorrect matching.

Not resetting j, causing infinite loops.

After finding a match, reset j to 0 to continue searching for other matches.

4fill in blank

hard

Fill both blanks to correctly update the LPS array inside the computeLPS function.

DSA Javascript

if (pattern[i] === pattern[[1]]) {
  len++;
  lps[[2]] = len;
  i++;
} else {
  // handle mismatch
}

Drag options to blanks, or click blank then click option'

Alen

Bi

C0

Dlen - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning lps[len] instead of lps[i].

Using wrong indices for comparison.

When characters match, increase len and assign it to lps at index i, then move i forward.

5fill in blank

hard

Fill all three blanks to complete the KMP search function's main loop correctly.

DSA Javascript

while (i < text.length) {
  if (pattern[[1]] === text[[2]]) {
    i++;
    j++;
    if (j === pattern.length) {
      result.push(i - j);
      j = [3];
    }
  } else if (j > 0) {
    j = lps[j - 1];
  } else {
    i++;
  }
}

Drag options to blanks, or click blank then click option'

Aj

Bi

C0

Dlps[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping i and j in comparisons.

Not resetting j properly after a match.

Compare pattern[j] with text[i], increment both indices on match, and reset j to 0 after a full match.

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