KMP Pattern Matching Algorithm in DSA Typescript

Mental Model

KMP finds a pattern in text by remembering where to restart after a mismatch, so it never rechecks characters unnecessarily.

Analogy: Imagine reading a book to find a phrase. Instead of going back to the start after a mismatch, you remember how much of the phrase matched and continue from there.

Text:  a b c d a b c d a b c d
Pattern:      a b c d a b c d
Prefix table: [0,0,0,0,1,2,3,4]

Dry Run Walkthrough

Input: text: 'ababcabcabababd', pattern: 'ababd'

Goal: Find the starting index of the pattern 'ababd' in the text

Step 1: Build prefix table for pattern 'ababd'

prefix: [0,0,1,2,0]

Why: Prefix table tells how far to jump back on mismatch

Step 2: Start matching pattern at text index 0

text: a b a b c a b c a b a b a b d
pattern: ↑ ↑ ↑ ↑ ↑
matched chars: 4

Why: Matched first 4 chars 'abab' successfully

Step 3: Mismatch at pattern index 4 ('d' vs 'c'), use prefix table to jump pattern index to 2

pattern index reset to 2, text index stays at 4

Why: Avoid rechecking matched chars, jump pattern index to prefix value

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

matched chars: 3 (pattern indices 2 to 4 matched with text indices 12 to 14)

Why: Resume matching from where prefix table suggests

Step 5: Mismatch again, jump pattern index to 0

pattern index reset to 0, text index moves forward

Why: No prefix match, restart pattern from beginning

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

pattern matched fully at text indices 10 to 14

Why: Pattern found starting at index 10

Result:

Pattern found at index 10

Annotated Code

DSA Typescript

class KMP {
  static buildPrefix(pattern: string): number[] {
    const prefix = Array(pattern.length).fill(0);
    let j = 0;
    for (let i = 1; i < pattern.length; i++) {
      while (j > 0 && pattern[i] !== pattern[j]) {
        j = prefix[j - 1];
      }
      if (pattern[i] === pattern[j]) {
        j++;
        prefix[i] = j;
      }
    }
    return prefix;
  }

  static search(text: string, pattern: string): number {
    if (pattern.length === 0) return 0;
    const prefix = this.buildPrefix(pattern);
    let j = 0;
    for (let i = 0; i < text.length; i++) {
      while (j > 0 && text[i] !== pattern[j]) {
        j = prefix[j - 1];
      }
      if (text[i] === pattern[j]) {
        j++;
      }
      if (j === pattern.length) {
        return i - j + 1;
      }
    }
    return -1;
  }
}

const text = 'ababcabcabababd';
const pattern = 'ababd';
const index = KMP.search(text, pattern);
console.log(index === -1 ? 'Pattern not found' : `Pattern found at index ${index}`);

while (j > 0 && pattern[i] !== pattern[j]) { j = prefix[j - 1]; }

jump pattern index back using prefix table on mismatch during prefix build

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

increment prefix length when characters match

while (j > 0 && text[i] !== pattern[j]) { j = prefix[j - 1]; }

jump pattern index back using prefix table on mismatch during search

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

advance pattern index on character match

if (j === pattern.length) { return i - j + 1; }

pattern fully matched, return start index

Output

Pattern found at index 10

Complexity Analysis

Time: O(n + m) because we build prefix table in O(m) and search in O(n) without backtracking

Space: O(m) for prefix table storing longest prefix lengths for pattern

vs Alternative: Naive search is O(n*m) because it restarts matching from next text char on mismatch, KMP avoids this by using prefix info

Edge Cases

empty pattern

returns 0 immediately, pattern found at start

DSA Typescript

if (pattern.length === 0) return 0;

pattern longer than text

returns -1, no match possible

DSA Typescript

for (let i = 0; i < text.length; i++) { ... }

pattern not in text

returns -1 after full search

DSA Typescript

return -1;

When to Use This Pattern

When you need to find a substring efficiently and want to avoid rechecking characters after mismatch, use KMP because it uses prefix info to skip ahead.

Common Mistakes

Mistake: Not updating pattern index j correctly on mismatch using prefix table
Fix: Use while loop to jump j back to prefix[j-1] until match or j=0

Mistake: Forgetting to increment j when characters match
Fix: Increment j inside if condition when text[i] === pattern[j]

Summary

Finds pattern in text efficiently by using prefix info to skip unnecessary checks

Use when searching substrings in large texts to improve over naive search

Remember prefix table tells how far to jump back on mismatch to avoid rechecking

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