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 proportion to the number of patterns.

Trie-based approach

Tries are efficient data structures for string search-related operations. Storing the patterns in the trie can help quickly retrieve items and improve search time. 

Let's consider an example where the text is PAPAYAPATAYA and the patterns to be searched are PAP and ATA. We insert the pattern strings into the trie and traverse over the text sequence. While iterating through the letters of the text, we check for matching characters in the trie and traverse down the trie path until the letters in the trie path and text sequence do not match further. At the end of the iteration of the text string, if all the trie nodes are visited, we can conclude that all pattern strings were successfully found in the trie.

The picture below represents the search procedure using a trie.

Complexity analysis

Let's assume that the average length of the pattern is $P$ and the size of the text is ...