KMP Pattern Matching Algorithm in DSA Javascript - Build from Scratch

KMP Pattern Matching Algorithm

📖 Scenario: You are building a simple text search tool that finds if a small pattern exists inside a larger text efficiently. This is useful in searching documents, DNA sequences, or logs.

🎯 Goal: Build the KMP (Knuth-Morris-Pratt) pattern matching algorithm step-by-step in JavaScript to find the first occurrence of a pattern in a text.

📋 What You'll Learn

Create an array called lps to store longest prefix suffix values

Create a function computeLPSArray to fill the lps array for the pattern

Create a function KMPSearch that uses lps to find the pattern in the text

Print the index of the first match or -1 if not found

💡 Why This Matters

🌍 Real World

Text search is used in editors, search engines, DNA sequence analysis, and log scanning to quickly find patterns.

💼 Career

Understanding KMP algorithm helps in software development roles involving string processing, data analysis, and algorithm optimization.

1

Create the text and pattern variables

Create two string variables called text and pattern with values 'ABABDABACDABABCABAB' and 'ABABCABAB' respectively.

DSA Javascript

# Your code here

Hint

Use const to declare text and pattern with the exact strings given.

2

Create the lps array and computeLPSArray function

Create an array called lps with length equal to pattern.length filled with zeros. Then create a function called computeLPSArray that takes pattern and lps as parameters and fills lps with longest prefix suffix values using the KMP preprocessing logic.

DSA Javascript

const text = 'ABABDABACDABABCABAB';
const pattern = 'ABABCABAB';
// Your code here

Hint

Initialize lps with zeros. Use a while loop and two pointers i and length to fill lps according to KMP rules.

3

Create the KMPSearch function using lps

Create a function called KMPSearch that takes pattern and text as parameters. Inside it, create an array lps and call computeLPSArray(pattern, lps). Then use two indexes i for text and j for pattern to find the first occurrence of pattern in text using the KMP algorithm. Return the index of the first match or -1 if not found.

DSA Javascript

const text = 'ABABDABACDABABCABAB';
const pattern = 'ABABCABAB';

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

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

// Your code here

Hint

Use two pointers i and j to scan text and pattern. Use lps to skip characters when mismatch happens.

4

Print the index of the first pattern match in the text

Call the function KMPSearch with pattern and text and print the returned index using console.log.

DSA Javascript

const text = 'ABABDABACDABABCABAB';
const pattern = 'ABABCABAB';

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

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

function KMPSearch(pattern, text) {
    const lps = new Array(pattern.length).fill(0);
    computeLPSArray(pattern, lps);

    let i = 0; // index for text
    let j = 0; // index for pattern

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

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

    return -1;
}

// Your code here

Hint

Call KMPSearch(pattern, text) and print the result with console.log.

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