KMP Pattern Matching Algorithm in DSA Typescript - Deep Dive

Overview - KMP Pattern Matching Algorithm

What is it?

The KMP Pattern Matching Algorithm is a way to find if a smaller word or pattern appears inside a bigger text quickly. It does this by remembering parts of the pattern it has already matched, so it doesn't waste time checking the same letters again. This makes searching faster than checking every letter one by one. It is useful when you want to find patterns in large texts efficiently.

Why it matters

Without KMP, searching for patterns in text would be slow, especially for big texts or many searches. This would make things like spell checking, searching documents, or DNA analysis take much longer. KMP saves time by skipping unnecessary checks, making computers faster and more efficient at finding patterns.

Where it fits

Before learning KMP, you should understand basic string matching and loops. After KMP, you can learn other advanced string algorithms like Rabin-Karp or suffix trees. KMP is a key step in mastering efficient text searching techniques.

Mental Model

Core Idea

KMP speeds up pattern searching by using information from previous matches to avoid rechecking characters.

Think of it like...

Imagine reading a book to find a sentence. If you find a mismatch, instead of going back to the start, you remember how much of the sentence matched and jump back only to the point where a new match could start.

Text:    a b c d a b c d a b c d
Pattern:       a b c d
          ↑ ↑ ↑ ↑
Match:    [check] [check] [check] [check]
If mismatch at position 4, jump pattern index back using prefix info instead of starting over.

Build-Up - 6 Steps

1

Foundation

Basic String Matching Concept

Concept: Understanding how to check if a pattern exists in a text by comparing characters one by one.

To find a pattern in text, start from the first character of text and pattern. Compare characters one by one. If all characters match, pattern found. If mismatch, move text index by one and start pattern from beginning again.

Result

This method works but can be slow if pattern and text have many repeated characters.

Knowing the simple matching method helps appreciate why KMP improves speed by avoiding repeated checks.

2

Foundation

Understanding Prefixes and Suffixes

Concept: Learning what prefixes and suffixes are in strings and how they relate to pattern matching.

A prefix is the start part of a string, and a suffix is the end part. For example, in 'abab', 'ab' is both a prefix and suffix. Recognizing these helps KMP know where to jump after mismatch.

Result

You can identify repeated parts inside the pattern that help skip unnecessary checks.

Understanding prefixes and suffixes is key to building the KMP table that speeds up searching.

3

Intermediate

Building the Longest Prefix Suffix Table

🤔Before reading on: do you think the table stores how many characters matched or something else? Commit to your answer.

Concept: Creating a table that tells how far to jump in the pattern after a mismatch based on prefix-suffix matches.

The table (also called lps) stores for each position the length of the longest prefix which is also a suffix. For example, for 'abab', at position 3, lps is 2 because 'ab' is prefix and suffix. This table helps decide where to continue matching after mismatch.

Result

With the lps table, the algorithm knows how many characters it can skip, avoiding rechecking.

Knowing how to build and use the lps table is the heart of KMP's efficiency.

4

Intermediate

Using the LPS Table in Pattern Search

🤔Before reading on: do you think the search restarts from the beginning after mismatch or uses the lps table to jump? Commit to your answer.

Concept: Applying the lps table to skip unnecessary comparisons during the search process.

When a mismatch happens, instead of moving text index by one and restarting pattern from zero, use lps to move pattern index to a position where matching can continue. This avoids rechecking characters that are known to match.

Result

The search runs faster, especially on texts with repeated patterns.

Using the lps table during search is what makes KMP faster than naive matching.

5

Advanced

Implementing KMP in TypeScript

🤔Before reading on: do you think the implementation needs two loops or just one? Commit to your answer.

Concept: Writing complete TypeScript code for KMP including lps table construction and search function.

The implementation has two main parts: one loop to build the lps table, and another to search the pattern in text using the lps table. Both loops run in linear time, making the whole algorithm efficient.

Result

The code finds all occurrences of the pattern in the text quickly and correctly.

Seeing the full code connects theory to practice and shows how KMP achieves linear time complexity.

6

Expert

KMP Algorithm Complexity and Edge Cases

🤔Before reading on: do you think KMP always runs in linear time regardless of input? Commit to your answer.

Concept: Understanding why KMP runs in O(n) time and how it handles tricky inputs like repeated characters or empty patterns.

KMP runs in O(n) because each character in text and pattern is processed at most twice. Edge cases like empty pattern or pattern longer than text are handled gracefully. Repeated characters in pattern do not slow down KMP due to lps table jumps.

Result

KMP is reliable and efficient even on worst-case inputs.

Knowing complexity and edge cases prepares you to use KMP confidently in real applications.

Under the Hood

KMP works by precomputing a table (lps) that stores the longest prefix which is also a suffix for each prefix of the pattern. During search, when a mismatch occurs, the algorithm uses this table to shift the pattern index to the right position without moving the text index back. This avoids re-examining characters that are known to match, ensuring each character is checked at most twice.

Why designed this way?

KMP was designed to improve naive string matching which can be very slow on repetitive patterns. By remembering partial matches, it avoids redundant comparisons. Alternatives like brute force were too slow, and hashing methods like Rabin-Karp can have collisions. KMP guarantees linear time without extra space for hashing.

Text:    a b a b a b c d
Pattern:     a b a b c d
          ↑ ↑ ↑ ↑ ↑ ↑
LPS:      0 0 1 2 3 0
Mismatch at last char, jump pattern index to lps[5]=0
Continue matching without moving text index back.

Myth Busters - 4 Common Misconceptions

Quick: Does KMP check every character in the text multiple times? Commit yes or no.

Common Belief: KMP checks every character in the text multiple times, so it is not faster than naive search.

Reality: KMP checks each character in the text at most twice, making it run in linear time.

Why it matters: Believing KMP is slow may prevent using it in performance-critical applications where it actually shines.

Quick: Is the lps table the same as the pattern itself? Commit yes or no.

Common Belief: The lps table just repeats the pattern characters or is the pattern itself.

Reality: The lps table stores lengths of longest prefix-suffix matches, not the pattern characters.

Why it matters: Misunderstanding lps leads to incorrect implementation and failed pattern searches.

Quick: Does KMP work only for alphabets or any characters? Commit yes or no.

Common Belief: KMP only works for alphabets or specific character sets.

Reality: KMP works for any characters, including numbers, symbols, or unicode.

Why it matters: Limiting KMP to alphabets restricts its use in real-world applications like searching code or data.

Quick: Can KMP handle empty patterns correctly? Commit yes or no.

Common Belief: KMP cannot handle empty patterns and will crash or behave unpredictably.

Reality: KMP can handle empty patterns by returning immediate matches or no matches safely.

Why it matters: Ignoring edge cases causes bugs in software using KMP for pattern matching.

Expert Zone

1

The lps table can be reused for multiple searches with the same pattern, saving computation time.

2

KMP's linear time guarantee holds even for pathological inputs with repeated characters, unlike naive search.

3

The algorithm can be adapted to find all occurrences of the pattern, not just the first, by continuing after matches.

When NOT to use

KMP is not ideal when patterns change frequently and preprocessing cost is high; in such cases, simpler algorithms or hashing methods like Rabin-Karp may be better. Also, for approximate matching (allowing errors), KMP is not suitable; specialized algorithms are needed.

Production Patterns

KMP is used in text editors for fast search, DNA sequence analysis for exact pattern matching, and network security tools to detect known signatures quickly. It is often combined with other algorithms for complex search tasks.

Connections

Finite Automata

KMP can be seen as a simplified finite automaton that processes input text to find patterns.

Understanding KMP helps grasp how automata process sequences efficiently without backtracking.

Dynamic Programming

Building the lps table uses overlapping subproblems similar to dynamic programming techniques.

Recognizing this connection clarifies how KMP reuses previous computations to save time.

Human Memory and Pattern Recognition

KMP mimics how humans remember partial matches to avoid rechecking from scratch.

This cross-domain link shows how algorithms can reflect cognitive strategies for efficiency.

Common Pitfalls

#1 Incorrectly resetting pattern index to zero after mismatch.

Wrong approach:

if (mismatch) { patternIndex = 0; textIndex++; }

Correct approach:

if (mismatch) { patternIndex = lps[patternIndex - 1]; }

Root cause:

Misunderstanding that KMP uses the lps table to jump pattern index instead of restarting.

#2 Building lps table incorrectly by not updating length properly.

Wrong approach:

while (i < pattern.length) { if (pattern[i] == pattern[len]) { lps[i] = len; i++; len++; } else { lps[i] = 0; i++; } }

Correct approach:

while (i < pattern.length) { if (pattern[i] == pattern[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } }

Root cause:

Not handling the fallback in lps computation causes wrong table and failed matches.

#3 Not handling empty pattern or text inputs.

Wrong approach:

function search(text, pattern) { /* no checks for empty strings */ }

Correct approach:

function search(text, pattern) { if (pattern.length === 0) return 0; if (text.length === 0) return -1; /* continue */ }

Root cause:

Ignoring edge cases leads to runtime errors or incorrect results.

Key Takeaways

KMP algorithm speeds up pattern searching by using a precomputed table to skip unnecessary comparisons.

The longest prefix suffix (lps) table is central to KMP and stores how much of the pattern can be reused after a mismatch.

KMP runs in linear time, checking each character at most twice, making it efficient for large texts.

Correct implementation requires careful construction of the lps table and proper use during the search phase.

Understanding KMP's mechanism helps in learning other advanced string algorithms and applying efficient search in real-world problems.

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