In brute force string matching, a mismatch results in reverting to characters previously compared, causing redundant comparisons. For instance, if there is a mismatch after checking the first four letters, the comparison starts again from the second letter of the text, which is redundant since we know the pattern's starting character does not appear within the checked range.

To eliminate this redundancy, we need a more efficient method.

Overview

The solution to the problem was presented by James H. Morris and Vaughan Pratt in 1970 with their algorithm, which avoids many unnecessary comparisons, making it more efficient than brute force string matching.

Key features include:

Comparisons are done from left to right.
The preprocessing phase has O(m) space and time complexity.
The searching phase has O(n+m) time complexity, independent of the alphabet size.
The algorithm performs at most 2n-1 comparisons during text scanning.
The delay is bounded by m.

Let’s examine the details. The main idea is to utilize the information gathered during pattern comparisons to identify potential matches, as shown in the diagram below.

morris-pratt-string-search-viz1.excalidraw

The Morris-Pratt algorithm skips certain comparisons by advancing to the next possible match location. To achieve this, the pattern must be preprocessed to determine these positions. This way, when a mismatch occurs, the algorithm knows precisely where to resume, avoiding redundant comparisons.

Generating the Table of Next Positions

This is the crucial aspect of the Morris-Pratt algorithm, which helps it overcome the limitations of brute force string searching. The following images illustrate this concept:

morris-pratt-string-search-viz2-distinct.excalidraw

If the pattern consists of unique letters, upon a mismatch, we compare the next text character with the first pattern character. However, if the pattern contains repeating characters, and a mismatch occurs after a repeating character, the next potential match begins from that repeating character, as shown below:

morris-pratt-string-search-viz3-non-distinct.excalidraw

The "next" table differs when the pattern has repeating characters: Finally, if the text contains multiple repeating characters, the "next" table will indicate their positions.

morris-pratt-string-search-viz4-multi-repeat.excalidraw

Once we have this table of potential "next" positions, we can start searching the text for our pattern.

morris-pratt-string-search-viz5-all-steps.excalidraw

Code

Implementing the Morris-Pratt algorithm is straightforward. First, preprocess the pattern, and then execute the search.

[{"language":"Java","code":"public class Solution {\n    // Preprocess the pattern and return the \"next\" table\n    private void preprocessMorrisPratt(String pattern, int[] nextTable) {\n        int i = 0;\n        int j = nextTable[0] = -1;\n        int len = pattern.length();\n\n        while (i < len) {\n            while (j > -1 && pattern.charAt(i) != pattern.charAt(j)) {\n                j = nextTable[j];\n            }\n            nextTable[++i] = ++j;\n        }\n    }\n\n    // Perform a stri

Related Tags