KMP Pattern Matching Algorithm in DSA Javascript - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching text and pattern

↓

Compare characters

↓

Move both i,j

↓

Check if j == pattern length

↓

Pattern found at i-j

↓

Continue matching until text end

First build the LPS array for the pattern, then scan the text comparing characters. On mismatch, use LPS to skip unnecessary comparisons.

Execution Sample

DSA Javascript

function KMPSearch(text, pattern) {
  const lps = buildLPS(pattern);
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) { i++; j++; }
    else if (j > 0) j = lps[j - 1];
    else i++;
    if (j === pattern.length) return i - j;
  }
  return -1;
}

This code searches for the pattern in the text using the KMP algorithm and returns the starting index of the first match or -1 if not found.

Execution Table

Step	Operation	i (text index)	j (pattern index)	LPS array	Action	Visual State
1	Build LPS array for pattern 'ABABC'	-	-	[0,0,1,2,0]	Computed LPS array	LPS: [0,0,1,2,0]
2	Compare text[0]='A' and pattern[0]='A'	0	0	[0,0,1,2,0]	Match: i=1, j=1	Match at i=0,j=0
3	Compare text[1]='B' and pattern[1]='B'	1	1	[0,0,1,2,0]	Match: i=2, j=2	Match at i=1,j=1
4	Compare text[2]='A' and pattern[2]='A'	2	2	[0,0,1,2,0]	Match: i=3, j=3	Match at i=2,j=2
5	Compare text[3]='B' and pattern[3]='B'	3	3	[0,0,1,2,0]	Match: i=4, j=4	Match at i=3,j=3
6	Compare text[4]='D' and pattern[4]='C'	4	4	[0,0,1,2,0]	Mismatch: j>0, set j=LPS[3]=2	Mismatch at i=4,j=4, j updated to 2
7	Compare text[4]='D' and pattern[2]='A'	4	2	[0,0,1,2,0]	Mismatch: j>0, set j=LPS[1]=0	Mismatch at i=4,j=2, j updated to 0
8	Compare text[4]='D' and pattern[0]='A'	4	0	[0,0,1,2,0]	Mismatch: j=0, increment i=5	Mismatch at i=4,j=0, i incremented
9	Compare text[5]='A' and pattern[0]='A'	5	0	[0,0,1,2,0]	Match: i=6, j=1	Match at i=5,j=0
10	Compare text[6]='B' and pattern[1]='B'	6	1	[0,0,1,2,0]	Match: i=7, j=2	Match at i=6,j=1
11	Compare text[7]='C' and pattern[2]='A'	7	2	[0,0,1,2,0]	Mismatch: j>0, set j=LPS[1]=0	Mismatch at i=7,j=2, j updated to 0
12	Compare text[7]='C' and pattern[0]='A'	7	0	[0,0,1,2,0]	Mismatch: j=0, increment i=8	Mismatch at i=7,j=0, i incremented
13	Compare text[8]='B' and pattern[0]='A'	8	0	[0,0,1,2,0]	Mismatch: j=0, increment i=9	Mismatch at i=8,j=0, i incremented
14	Compare text[9]='C' and pattern[0]='A'	9	0	[0,0,1,2,0]	Mismatch: j=0, increment i=10	Mismatch at i=9,j=0, i incremented
15	i=10 equals text length=10	10	0	[0,0,1,2,0]	End: pattern not found	Search ends, no match

💡 i reached text length 10, no full pattern match found

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14	Final
i (text index)	0	1	2	3	4	4	4	5	6	7	7	8	9	10	10
j (pattern index)	0	1	2	3	4	2	0	0	1	2	0	0	0	0	0
LPS array	-	-	-	-	-	-	-	-	-	-	-	-	-	-	[0,0,1,2,0]

Key Moments - 3 Insights

Why do we update j to LPS[j-1] on mismatch instead of resetting j to 0?

Because LPS[j-1] tells us the longest prefix which is also suffix, so we can skip rechecking characters that we know match. See steps 6 and 7 where j jumps back instead of resetting.

Why do we increment i only when j is zero on mismatch?

When j is zero, no prefix matched yet, so we must move forward in text. When j > 0, we use LPS to shift pattern without moving i. See step 8 where i increments because j=0.

What does the LPS array represent and how is it used?

LPS array stores lengths of longest proper prefix which is also suffix for each pattern prefix. It helps to avoid rechecking characters on mismatch. Built in step 1 and used in mismatch handling.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the new value of j after mismatch?

A 0

B 4

C 2

D 3

💡 Hint

Check the 'Action' and 'j (pattern index)' columns at step 6 in the execution_table.

At which step does the text index i first increment without increasing j?

A Step 8

B Step 7

C Step 6

D Step 9

💡 Hint

Look for where 'j=0' and 'i' increments in the execution_table rows.

If the pattern was 'ABAB' instead of 'ABABC', what would be the last value in the LPS array?

A 1

B 2

C 3

D 0

💡 Hint

Recall how LPS array is built and check the pattern length and prefix-suffix matches.

Concept Snapshot

KMP Pattern Matching Algorithm:
- Build LPS (Longest Prefix Suffix) array for pattern
- Use LPS to skip unnecessary comparisons on mismatch
- Compare text and pattern chars with indices i, j
- On match: i++, j++
- On mismatch and j>0: j = LPS[j-1]
- On mismatch and j=0: i++
- If j == pattern length, pattern found at i-j

Full Transcript

The KMP algorithm first builds an LPS array for the pattern, which stores the longest prefix that is also a suffix for each prefix of the pattern. Then it scans the text with two pointers i and j for text and pattern respectively. When characters match, both pointers move forward. On mismatch, if j is not zero, j is updated to LPS[j-1] to avoid rechecking characters. If j is zero, i moves forward. This process continues until the pattern is found or the text ends. The LPS array helps skip unnecessary comparisons, making the search efficient.

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