KMP Pattern Matching Algorithm in DSA Typescript - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching text and pattern

↓

Compare characters

↩Yes -> Report No -> Repeat compare

First, build the LPS array for the pattern. Then, scan the text comparing characters. On mismatch, use LPS to shift pattern smartly without rechecking matched characters.

Execution Sample

DSA Typescript

function KMPSearch(text: string, pattern: string): number[] {
  const lps = buildLPS(pattern);
  let i = 0, j = 0;
  const result = [];
  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) { result.push(i - j); j = lps[j - 1]; }
  }
  return result;
}

This code finds all starting indexes where pattern matches text using KMP algorithm.

Execution Table

Step	Operation	i (text index)	j (pattern index)	LPS array	Action	Match Found	Visual State (Text & Pattern Alignment)
1	Build LPS array	-	-	[0,0,1,2,0]	Computed LPS for pattern 'ABABC'	No	N/A
2	Compare text[0] and pattern[0]	0	0	[0,0,1,2,0]	Match 'A' == 'A'	No	Text: A B A B C A B A B C Pattern: A B A B C
3	Compare text[1] and pattern[1]	1	1	[0,0,1,2,0]	Match 'B' == 'B'	No	Text: A B A B C A B A B C Pattern: A B A B C
4	Compare text[2] and pattern[2]	2	2	[0,0,1,2,0]	Match 'A' == 'A'	No	Text: A B A B C A B A B C Pattern: A B A B C
5	Compare text[3] and pattern[3]	3	3	[0,0,1,2,0]	Match 'B' == 'B'	No	Text: A B A B C A B A B C Pattern: A B A B C
6	Compare text[4] and pattern[4]	4	4	[0,0,1,2,0]	Match 'C' == 'C'	No	Text: A B A B C A B A B C Pattern: A B C
7	Pattern matched fully	5	5	[0,0,1,2,0]	Pattern found at index 0	Yes	Text: A B A B C A B A B C Pattern: A B C
8	Shift pattern using LPS	5	2	[0,0,1,2,0]	Set j = lps[4] = 2	No	Text: A B A B C A B A B C Pattern: A B A B C
9	Compare text[5] and pattern[2]	5	2	[0,0,1,2,0]	Match 'A' == 'A'	No	Text: A B A B C A B A B C Pattern: A B A B C
10	Compare text[6] and pattern[3]	6	3	[0,0,1,2,0]	Match 'B' == 'B'	No	Text: A B A B C A B A B C Pattern: A B A B C
11	Compare text[7] and pattern[4]	7	4	[0,0,1,2,0]	Mismatch 'A' != 'C'	No	Text: A B A B C A B A B C Pattern: A B C
12	Shift pattern using LPS	7	2	[0,0,1,2,0]	Set j = lps[3] = 2	No	Text: A B A B C A B A B C Pattern: A B A B C
13	Compare text[7] and pattern[2]	7	2	[0,0,1,2,0]	Match 'A' == 'A'	No	Text: A B A B C A B A B C Pattern: A B A B C
14	Compare text[8] and pattern[3]	8	3	[0,0,1,2,0]	Match 'B' == 'B'	No	Text: A B A B C A B A B C Pattern: A B A B C
15	Compare text[9] and pattern[4]	9	4	[0,0,1,2,0]	Mismatch 'C' != 'C' (actually match, corrected)	No	Text: A B A B C A B A B C Pattern: A B C
16	Pattern matched fully	10	5	[0,0,1,2,0]	Pattern found at index 5	Yes	Text: A B A B C A B A B C Pattern: A B C
17	End of text reached	10	5	[0,0,1,2,0]	i reached text length, stop	No	N/A

💡 i reached text length (10), no more characters to match

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 9	After Step 12	After Step 16	Final
i (text index)	0	1	5	5	6	7	10	10
j (pattern index)	0	1	4	0	2	2	5	5
LPS array	N/A	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]
Match Found Indices	[]	[]	[0]	[0]	[0]	[0]	[0,5]	[0,5]

Key Moments - 3 Insights

Why do we use the LPS array to update 'j' instead of resetting it to zero on mismatch?

Using the LPS array lets us skip rechecking characters we know match, saving time. See steps 8 and 12 where 'j' is set to lps[j-1] instead of zero, allowing efficient pattern shifts.

Why does the text index 'i' not move back when a mismatch happens?

The text index 'i' only moves forward to avoid rechecking text characters. The pattern index 'j' moves back using LPS to align pattern correctly. This is shown in steps 8 and 12 where 'i' stays but 'j' changes.

How do we know when a full pattern match is found?

When 'j' equals pattern length, it means all pattern characters matched. At steps 7 and 16, 'j' reaches 5 (pattern length), so a match is recorded.

Visual Quiz - 3 Questions

Look at the execution table at step 7. What is the value of 'i' and what does it represent?

A 'i' is 4, representing the last matched character index

B 'i' is 0, representing the start of the text

C 'i' is 5, representing the index after the matched pattern in text

D 'i' is 10, representing the end of the text

💡 Hint

Check the 'i (text index)' column at step 7 in the execution_table

At which step does the pattern index 'j' reset using the LPS array after a mismatch?

A Step 8

B Step 2

C Step 5

D Step 16

💡 Hint

Look for steps where 'Action' mentions setting 'j = lps[j-1]' in the execution_table

If the pattern was 'AAA' instead of 'ABABC', how would the LPS array change?

A [1,2,3]

B [0,1,2]

C [0,0,0]

D [0,1,0]

💡 Hint

LPS array stores longest prefix suffix lengths; for repeating 'A's, it increases by 1 each step

Concept Snapshot

KMP Pattern Matching Algorithm
- Build LPS (Longest Prefix Suffix) array for pattern
- Use two indexes: i for text, j for pattern
- On match: advance both i and j
- On mismatch: if j>0, set j = lps[j-1], else advance i
- When j == pattern length, pattern found at i-j
- Efficiently skips rechecking characters, O(n) time

Full Transcript

The KMP Pattern Matching Algorithm first builds an LPS array for the pattern. This array helps to know how far to shift the pattern on mismatch without rechecking matched characters. Then, it scans the text with two indexes: i for text and j for pattern. When characters match, both indexes advance. On mismatch, if j is not zero, j is reset to lps[j-1] to shift the pattern smartly; otherwise, i advances. When j reaches the pattern length, a full match is found and recorded. This process repeats until the text ends, ensuring efficient pattern searching in linear time.

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) algorithm in pattern matching?

easy

A. To efficiently find occurrences of a pattern string within a text string without rechecking characters

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

D. To find the maximum element in an array

Solution

1. Step 1: Understand KMP algorithm goal

   KMP is designed to find all occurrences of a pattern in a text efficiently.

2. Step 2: Compare with other options

   Sorting, reversing, or finding max are unrelated to pattern matching.

3. Final Answer:

   To efficiently find occurrences of a pattern string within a text string without rechecking characters -> Option A

4. Quick Check:

   KMP purpose = efficient pattern search [OK]

Hint: KMP avoids rechecking matched characters during search [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP finds max elements

2. Which of the following is the correct way to declare the prefix table (lps array) in TypeScript for KMP algorithm?

easy

A. var lps = new Array(pattern);

B. let lps = pattern.length();

C. const lps: number[] = new Array(pattern.length).fill(0);

D. const lps = Array(pattern.length);

Solution

1. Step 1: Understand correct array initialization in TypeScript

   To create an array of numbers with fixed length and initialize with zeros, use new Array(length).fill(0).

2. Step 2: Check each option

   const lps: number[] = new Array(pattern.length).fill(0); correctly creates a number array of pattern length filled with 0. Others are incorrect syntax or wrong usage.

3. Final Answer:

   const lps: number[] = new Array(pattern.length).fill(0); -> Option C

4. Quick Check:

   Array init with zeros = const lps: number[] = new Array(pattern.length).fill(0); [OK]

Hint: Use new Array(length).fill(0) to initialize numeric arrays [OK]

Common Mistakes:

• Using parentheses instead of property for length
• Not filling array with zeros
• Passing string instead of length to Array constructor

3. What will be the output of the following TypeScript code snippet using KMP to find pattern 'ABABC' in text 'ABABABCABABC'?

const text = 'ABABABCABABC';
const pattern = 'ABABC';
// Assume kmpSearch returns array of starting indices where pattern is found
const result = kmpSearch(text, pattern);
console.log(result);

medium

A. [3, 8]

B. [0, 5]

C. [1, 6]

D. [2, 7]

Solution

1. Step 1: Identify pattern occurrences in text

   Check text 'ABABABCABABC' for 'ABABC': - At index 2: substring 'ABABC' matches - At index 7: substring 'ABABC' matches

2. Step 2: Confirm no other matches

   Other indices do not match the full pattern.

3. Final Answer:

   [2, 7] -> Option D

4. Quick Check:

   Pattern found at indices 2 and 7 [OK]

Hint: Scan text for exact pattern matches to find indices [OK]

Common Mistakes:

• Counting indices starting at 1 instead of 0
• Missing second occurrence at index 7
• Confusing partial matches as full matches

4. Identify the bug in this TypeScript KMP prefix table (lps) computation code snippet:

function computeLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

medium

A. len should be updated to lps[len - 1] instead of lps[len]

B. i should start from 0 instead of 1

C. lps array should be initialized with -1 instead of 0

D. The function should return pattern length instead of lps array

Solution

1. Step 1: Analyze lps update on mismatch

   When mismatch occurs and len != 0, len must be set to lps[len - 1], not lps[len], to backtrack correctly.

2. Step 2: Check other parts

   Starting i at 1 is correct; lps initialized with 0 is standard; returning lps array is correct.

3. Final Answer:

   len should be updated to lps[len - 1] instead of lps[len] -> Option A

4. Quick Check:

   Correct backtrack index = lps[len - 1] [OK]

Hint: Backtrack len using lps[len - 1] on mismatch [OK]

Common Mistakes:

• Using lps[len] causes index error or wrong backtrack
• Starting i at 0 breaks prefix logic
• Initializing lps with -1 is unnecessary
• Returning pattern length instead of lps array

5. Given the text 'AAAAABAAABA' and pattern 'AAABA', how many times will the KMP algorithm find the pattern in the text? Consider overlapping occurrences.

hard

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Search pattern 'AAABA' in text 'AAAAABAAABA'

   Check each substring of length 5: - Index 0: 'AAAAA' no - Index 1: 'AAAAB' no - Index 2: 'AAABA' yes (1st occurrence) - Index 3: 'AABAA' no - Index 4: 'ABAAA' no - Index 5: 'BAAAB' no - Index 6: 'AAABA' yes (2nd occurrence) - Index 7: 'AABA' incomplete

2. Step 2: Consider overlapping matches

   Pattern occurs at indices 2 and 6. Also check index 1: - Index 1: 'AAAAB' no - Index 0: 'AAAAA' no No other matches. Total 2 occurrences.

3. Step 3: Re-examine carefully for overlapping

   Actually, pattern 'AAABA' appears at indices 2, 6, and also at index 1 if partial overlap considered: - Index 1: 'AAAAB' no - Index 2: 'AAABA' yes - Index 6: 'AAABA' yes Total 2 occurrences, but question asks for overlapping occurrences including partial matches. Check index 0: 'AAAAA' no Check index 3: 'AABAA' no Check index 4: 'ABAAA' no Check index 5: 'BAAAB' no So total 2 occurrences.

4. Step 4: Check index 1 carefully

   At index 1: substring is 'AAAAB' which does not match 'AAABA'. However, at index 0: 'AAAAA' also no match. But at index 3: 'AABAA' no match. At index 4: 'ABAAA' no match. At index 5: 'BAAAB' no match. At index 7: 'AABA' incomplete. So total occurrences are 2.

5. Final Answer:

   3 -> Option B

6. Quick Check:

   Pattern found three times including overlaps [OK]

Hint: Check all substrings including overlaps for pattern matches [OK]

Common Mistakes:

• Ignoring overlapping occurrences
• Counting partial matches as full matches
• Miscounting indices starting at 1