Understanding the KMP Failure Function and Its O(n) Time Complexity

The Knuth–Morris–Pratt (KMP) algorithm is a well-known method for string pattern matching, crucial for many computer science applications like text searching, computational biology, and automata theory. The core component of the KMP algorithm is its failure function (also known as the prefix function), which can be computed efficiently in $O(n)$ time, where $n$ is the length of the pattern.

The Role of the Failure Function

The failure function allows the KMP algorithm to avoid unnecessary comparisons by using knowledge of previously matched characters. It provides a way to shift the pattern efficiently when a mismatch occurs, without having to re-check previously matched characters.

Definition of the Failure Function

The failure function, usually denoted `π` or `lps` (longest proper prefix that is also a suffix), for a pattern `P[0..n-1]`, is defined as follows:

• `π[i]` is the length of the longest proper prefix of the substring `P[0..i]` which is also a suffix of this substring.

Computation of the Failure Function: A Step-by-Step Explanation

To understand why the failure function can be computed in $O(n)$ time, let's delve into the mechanics of its computation.

Algorithm Outline

1. Initialization:
   • Set `π[0] = 0`. The longest proper prefix which is also a suffix for the single character `P[0]` is obviously 0.
2. Iterative Computation:
   • For each position `i` from 1 to `n-1`, we perform the following:
     • Initialize `j` to be `π[i-1]` (the value for the previous character).
     • While `j` is greater than 0 and `P[j]` does not match `P[i]`, update `j = π[j-1]`.
     • If `P[j]` == `P[i]`, then set `j = j + 1`.
     • Set `π[i] = j`.

Key Insight: Pattern Matching within the Pattern

The critical insight facilitating $O(n)$ time complexity stems from the manner in which `j` (the index of the prefix) is adjusted:

• The value of `j` could decrease at most as many times as it increases, ensuring the combined complexity of both operations over the entire loop is linear.

This behavior effectively ensures that in the worst-case scenario, each character in the pattern is only processed a constant number of times, leading to $O(n)$ overall complexity.

Example Demonstration

Consider the pattern `ABABCABAB`. Let's manually compute the failure function:

• Initialize `π = [0, 0, 0, 0, 0, 0, 0, 0, 0]`.
• Start iterating from `i = 1`.

Summary and Key Points

Additional Insights

• The KMP algorithm, complemented by the failure function, demonstrates how internal structure (prefix-suffix relationships) can be exploited to achieve efficient pattern search without the need for backtracking over the text.
• The linear-time precomputation of the failure function significantly enhances the practical performance of the KMP algorithm especially when dealing with large text databases.

This in-depth understanding of the failure function reveals why the KMP algorithm is both theoretically interesting and practically efficient for any string matching problem.