Introduction to Pattern Matching Using Tries

Pattern matching

In strings, pattern matching means checking the presence of a given sequence of characters called a pattern in a more extensive series of letters or characters, which we call text.

Some examples of the problems associated with pattern matching include finding exact matches, partial matches, both exact and partial matches—as well as just the first match and the position of each match within the text. 

Brute-force approach

Let's look at an example to understand a simple pattern-matching problem.

The picture above shows that the pattern PA occurs three times in the text. In the above scenario, we use a sliding window and move the pattern string through the text one character at a time and look for a match.

Complexity analysis

Let's assume that the length of the pattern is $P$ and the size of the text is $T$. The time complexity of this approach is $O(P \times T)$. Since each pattern will need a separate iteration on the entire text, the time complexity increases in ...