KMP Pattern Matching Algorithm in DSA Javascript - Deep Dive

Overview - KMP Pattern Matching Algorithm

What is it?

The KMP Pattern Matching Algorithm is a way to find if a smaller string (pattern) appears inside a bigger string (text). It does this quickly by remembering parts of the pattern it has already checked, so it doesn't waste time repeating work. This makes searching faster than checking every position one by one.

Why it matters

Without KMP, searching for patterns in text can be slow, especially with large texts or many searches. This would make tasks like searching documents, DNA sequences, or logs inefficient and frustrating. KMP speeds up these searches, saving time and computing power, which is important in many real-world applications.

Where it fits

Before learning KMP, you should understand basic string handling and simple pattern searching methods like the naive approach. After KMP, you can explore other advanced string algorithms like Rabin-Karp or suffix trees, and learn about algorithm optimization and complexity analysis.

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 starting over from the next letter, you remember how much of the sentence matched before and jump to the right spot to continue, saving time.

Text:    a b c d a b c d a b c d
Pattern:       a b c d a b

KMP uses a table to know how far to jump back in the pattern when a mismatch happens, avoiding rechecking matched letters.

Build-Up - 6 Steps

1

Foundation

Understanding Basic Pattern Search

Concept: Learn how simple pattern search works by checking each position in the text.

The naive method checks every position in the text to see if the pattern starts there. For example, to find 'abc' in 'xabcd', it checks 'xab', then 'abc', then 'bcd'. This is simple but can be slow if the text and pattern are large.

Result

The naive search finds the pattern but may check many unnecessary positions.

Knowing the naive method helps understand why KMP improves search speed by avoiding repeated checks.

2

Foundation

What is the Prefix Table?

Concept: Introduce the prefix table (also called LPS array) that stores longest prefix-suffix lengths.

The prefix table tells us, for each position in the pattern, the length of the longest prefix that is also a suffix up to that point. For example, for 'abab', the prefix table is [0,0,1,2]. This helps KMP know where to jump after a mismatch.

Result

The prefix table summarizes pattern structure to guide efficient searching.

Understanding the prefix table is key to how KMP avoids rechecking characters.

3

Intermediate

Building the Prefix Table Step-by-Step

🤔Before reading on: do you think the prefix table can have values larger than the current index? Commit to your answer.

Concept: Learn how to build the prefix table by comparing pattern characters and tracking matches.

Start with index 1 in the pattern. Compare the current character with the character at the length of the previous longest prefix. If they match, increase the length and set it in the table. If not, reduce the length using the table until a match or zero is found. Repeat until the table is complete.

Result

A complete prefix table that guides the search jumps.

Knowing how to build the prefix table manually helps understand the logic behind KMP's efficiency.

4

Intermediate

Using the Prefix Table in Search

🤔Before reading on: when a mismatch happens, do you think KMP restarts from the next text character or uses the prefix table to jump? Commit to your answer.

Concept: Apply the prefix table to skip unnecessary comparisons during the search.

When characters match, move forward in both text and pattern. On mismatch, use the prefix table to move the pattern index back to the longest prefix-suffix position instead of starting over. Continue until the pattern is found or text ends.

Result

Faster search that avoids rechecking matched characters.

Using the prefix table during search is what makes KMP faster than naive methods.

5

Advanced

Implementing KMP in JavaScript

🤔Before reading on: do you think the prefix table is built before or during the search? Commit to your answer.

Concept: Write complete JavaScript code for prefix table creation and pattern search using KMP.

First, build the prefix table for the pattern. Then, iterate over the text comparing characters. On match, move both indices. On mismatch, use the prefix table to adjust the pattern index. Return the starting index of the pattern in the text or -1 if not found. Example code: function buildPrefixTable(pattern) { const lps = Array(pattern.length).fill(0); let length = 0; 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; } function kmpSearch(text, pattern) { const lps = buildPrefixTable(pattern); let i = 0; // text index let j = 0; // pattern index while (i < text.length) { if (text[i] === pattern[j]) { i++; j++; if (j === pattern.length) { return i - j; // pattern found } } else { if (j !== 0) { j = lps[j - 1]; } else { i++; } } } return -1; // not found }

Result

The function returns the index where the pattern starts or -1 if not found.

Seeing the full code connects theory to practice and shows how prefix table and search work together.

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: Understand KMP's time complexity and how it handles tricky patterns and inputs.

KMP runs in O(n + m) time, where n is text length and m is pattern length. This is because each character is processed at most twice. Edge cases include patterns with repeated characters or empty strings. KMP handles these gracefully by using the prefix table to avoid redundant checks.

Result

KMP is efficient and reliable even on difficult inputs.

Knowing KMP's complexity and edge case handling helps trust it in production and avoid bugs.

Under the Hood

KMP works by precomputing a prefix table that stores the longest proper prefix which is also a suffix for each substring of the pattern. During search, when a mismatch occurs, the algorithm uses this table to shift the pattern to the right position without re-examining characters that have already matched. This avoids backtracking in the text and ensures linear time complexity.

Why designed this way?

KMP was designed to improve on naive search by eliminating repeated comparisons. Early string search algorithms restarted from the next character after a mismatch, causing inefficiency. KMP's prefix table idea was a breakthrough to reuse previous match information, balancing preprocessing cost with faster search.

Text:  a b c d a b c d a b c d
Pattern:    a b c d a b

Prefix Table (LPS): [0,0,0,0,1,2]

Search flow:
[Match] -> move forward
[Mismatch] -> jump pattern index to LPS value

┌─────────────┐
│ Build LPS   │
│ for pattern │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Search text │
│ using LPS   │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Result:     │
│ index or -1 │
└─────────────┘

Myth Busters - 4 Common Misconceptions

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

Common Belief: KMP might check some text characters more than once because of backtracking.

Reality: KMP checks each text character at most once, ensuring linear time complexity.

Why it matters: Believing KMP backtracks can lead to underestimating its efficiency and avoiding it unnecessarily.

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

Common Belief: The prefix table is just a copy or rearrangement of the pattern.

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

Why it matters: Misunderstanding the prefix table can cause confusion in building and using it correctly.

Quick: Can KMP be used to find multiple occurrences of a pattern in one pass? Commit to yes or no.

Common Belief: KMP only finds the first occurrence and must restart for others.

Reality: KMP can find all occurrences in one pass by continuing the search after each match.

Why it matters: Knowing this allows efficient multiple pattern searches without restarting.

Quick: Does KMP work only on English letters? Commit to yes or no.

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

Reality: KMP works on any sequence of characters or symbols, including Unicode or binary data.

Why it matters: This broad applicability makes KMP useful in many domains beyond text.

Expert Zone

1

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

2

KMP's linear time guarantee depends on careful implementation; subtle bugs in prefix table construction can degrade performance.

3

In some cases, other algorithms like Boyer-Moore outperform KMP by skipping more characters, especially on large alphabets.

When NOT to use

Avoid KMP when the pattern or text is very small, as the overhead of building the prefix table may not pay off. For approximate matching or very large alphabets, consider algorithms like Rabin-Karp or Boyer-Moore.

Production Patterns

KMP is used in text editors for fast search, bioinformatics for DNA sequence matching, and network security for pattern detection in data streams. It is often combined with other algorithms for hybrid search solutions.

Connections

Finite Automata

KMP's prefix table is similar to the state transitions in finite automata used for pattern recognition.

Understanding KMP helps grasp how automata process input efficiently by remembering states.

Dynamic Programming

Building the prefix table uses overlapping subproblems and reuses previous results, a key idea in dynamic programming.

Seeing prefix table construction as dynamic programming clarifies how KMP avoids redundant work.

Human Memory and Learning

KMP mimics how humans remember partial matches to avoid rechecking from scratch when searching for patterns.

This connection shows how algorithms can reflect natural cognitive strategies for efficiency.

Common Pitfalls

#1 Incorrect prefix table construction leading to wrong jump positions.

Wrong approach:

function buildPrefixTable(pattern) {
const lps = Array(pattern.length).fill(0);
let length = 0;
for (let i = 1; i < pattern.length; i++) {
if (pattern[i] === pattern[length]) {
length++;
lps[i] = length;
} else {
lps[i] = 0; // wrong: does not update length properly
}
}
return lps;
}

Correct approach:

function buildPrefixTable(pattern) {
const lps = Array(pattern.length).fill(0);
let length = 0;
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;
}

Root cause:

Misunderstanding how to fallback in prefix table construction causes incorrect values and search failures.

#2 Not using the prefix table on mismatch during search.

Wrong approach:

function kmpSearch(text, pattern) {
const lps = buildPrefixTable(pattern);
let i = 0, j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++; j++;
if (j === pattern.length) return i - j;
} else {
j = 0; // wrong: resets pattern index instead of using lps
i++;
}
}
return -1;
}

Correct approach:

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

Root cause:

Ignoring the prefix table during mismatch wastes KMP's efficiency advantage.

Key Takeaways

KMP algorithm speeds up pattern searching by using a prefix table to avoid rechecking characters.

The prefix table stores the longest prefix which is also a suffix for each pattern position, guiding efficient jumps.

Building the prefix table correctly is crucial for KMP's linear time performance.

KMP handles all inputs in O(n + m) time, making it reliable for large texts and patterns.

Understanding KMP connects to broader concepts like automata and dynamic programming, enriching algorithm knowledge.

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