Why can the KMP failure function be computed in On time?
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
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 time, where 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 time, let's delve into the mechanics of its computation.
Algorithm Outline
- Initialization:
- Set `π[0] = 0`. The longest proper prefix which is also a suffix for the single character `P[0]` is obviously 0.
- 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 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 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`.
| i | P[i] | j | Action | π |
| 1 | B | 0 | B != A, no match, π[1] = 0 | [0,0,0,0,0,0,0,0,0] |
| 2 | A | 0 | A = A, match, increase j to 1, π[2] = 1 | [0,0,1,0,0,0,0,0,0] |
| 3 | B | 1 | B = B, match, increase j to 2, π[3] = 2 | [0,0,1,2,0,0,0,0,0] |
| 4 | C | 2 | C != A, mismatch, jump to π\[1] = 0 | [0,0,1,2,0,0,0,0,0] |
| 4 | C | 0 | C != A, no match, π[4] = 0 | [0,0,1,2,0,0,0,0,0] |
| 5 | A | 0 | A = A, match, increase j to 1, π[5] = 1 | [0,0,1,2,0,1,0,0,0] |
| 6 | B | 1 | B = B, match, increase j to 2, π[6] = 2 | [0,0,1,2,0,1,2,0,0] |
| 7 | A | 2 | A = A, match, increase j to 3, π[7] = 3 | [0,0,1,2,0,1,2,3,0] |
| 8 | B | 3 | B = B, match, increase j to 4, π[8] = 4 | [0,0,1,2,0,1,2,3,4] |
Summary and Key Points
| Concept | Description | ||
| Failure Function | Table showing longest proper prefix-suffix match | ||
| Initialization | π\[0] = 0 initially | ||
| Update Rule | If match, increment; if mismatch, fall back using π\[j-1] | ||
| Example Pattern | For ABABCABAB, results in π = \[0,0,1,2,0,1,2,3,4] | ||
| Complexity Reasoning | Total operations per character $= \leq \\lvert P \\rvert $securing$O(n)$ time |
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.
