KMP Pattern Matching Algorithm in DSA Javascript

Mental Model

KMP finds a pattern in text by skipping unnecessary checks using a precomputed table of longest prefix-suffix matches.

Analogy: Imagine searching a word in a book by remembering parts of the word you matched before, so you don't start over from scratch each time you find a mismatch.

Text:  A B C D A B C D A B C
Pattern:      A B C D A B
          ↑ ↑ ↑ ↑ ↑ ↑
LPS:    [0,0,0,0,1,2]

Dry Run Walkthrough

Input: text: 'ABABDABACDABABCABAB', pattern: 'ABABCABAB'

Goal: Find all starting indices where the pattern appears in the text efficiently.

Step 1: Compute LPS array for pattern 'ABABCABAB'

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

Why: LPS helps us know how far to jump in pattern on mismatch.

Step 2: Start matching pattern at text index 0

Text: [A] B A B D A B A C D A B A B C A B A B
Pattern: [A] B A B C A B A B

Why: First characters match, continue.

Step 3: Match pattern index 1 with text index 1

Text: A [B] A B D A B A C D A B A B C A B A B
Pattern: A [B] A B C A B A B

Why: Characters match, continue.

Step 4: Match pattern index 2 with text index 2

Text: A B [A] B D A B A C D A B A B C A B A B
Pattern: A B [A] B C A B A B

Why: Characters match, continue.

Step 5: Mismatch at pattern index 4 and text index 4 ('C' vs 'D'), use LPS to shift pattern

Text: A B A B [D] A B A C D A B A B C A B A B
Pattern: A B A B C A B A B
Shift pattern index to LPS[3]=2

Why: Mismatch found, jump pattern index to 2 to avoid rechecking matched chars.

Step 6: Continue matching from pattern index 2 and text index 4

Text: A B A B D [A] B A C D A B A B C A B A B
Pattern: A B [A] B C A B A B

Why: After shift, continue matching to find full pattern.

Step 7: Continue matching until full pattern matched at text index 10

Text: A B A B D A B A C D [A B A B C A B A B]
Pattern: A B A B C A B A B

Why: Full pattern matched, record index 10.

Result:

Pattern found at indices: 10

Annotated Code

DSA Javascript

class KMP {
  static computeLPS(pattern) {
    const lps = Array(pattern.length).fill(0);
    let length = 0; // length of previous longest prefix suffix
    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;
  }

  static search(text, pattern) {
    const lps = this.computeLPS(pattern);
    const result = [];
    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) {
        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;
  }
}

const text = 'ABABDABACDABABCABAB';
const pattern = 'ABABCABAB';
const matches = KMP.search(text, pattern);
console.log('Pattern found at indices:', matches.join(', '));

while (i < pattern.length) { ... }

build LPS array by comparing prefix and suffix

if (pattern[j] === text[i]) { i++; j++; }

advance both pointers on match

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

pattern found, record index and reset j using LPS

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

on mismatch, use LPS to avoid rechecking matched chars

Output

Pattern found at indices: 10

Complexity Analysis

Time: O(n + m) because we scan the text and pattern once each using the LPS table to skip comparisons

Space: O(m) for the LPS array storing longest prefix-suffix lengths for the pattern

vs Alternative: Naive search is O(n*m) because it restarts matching from next text index on mismatch; KMP improves by skipping redundant checks

Edge Cases

Empty pattern

Returns empty matches immediately, no search needed

DSA Javascript

while (i < pattern.length) { ... }

Pattern longer than text

No matches found, returns empty array

DSA Javascript

while (i < text.length) { ... }

Pattern equals text

Returns index 0 as match

DSA Javascript

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

When to Use This Pattern

When you need to find a pattern inside a large text efficiently and want to avoid rechecking characters after mismatches, use KMP pattern matching because it uses a precomputed table to skip unnecessary comparisons.

Common Mistakes

Mistake: Not updating the pattern index j correctly after a mismatch using the LPS array
Fix: Set j = lps[j - 1] on mismatch instead of resetting to zero

Mistake: Incorrectly computing the LPS array causing infinite loops or wrong jumps
Fix: Carefully update length and i pointers in LPS computation to reflect longest prefix-suffix

Summary

Finds all occurrences of a pattern in a text efficiently using a longest prefix-suffix table.

Use when searching for patterns in large texts where naive search is too slow.

The key insight is precomputing how much to shift the pattern on mismatch to avoid rechecking matched characters.

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