Problem Statement: Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

As discussed in the previous post, we discussed that there are two ways efficiently solve the above problem.

1) Preprocess Pattern: KMP Algorithm, Rabin Karp Algorithm, Finite Automata, Boyer Moore Algorithm.

2) Preoprocess Text: Suffix Tree

The best possible time complexity achieved by first (preprocssing pattern) is O(n) and by second (preprocessing text) is O(m) where m and n are lengths of pattern and text respectively.

Note that the second way does the searching only in O(m) time and it is preferred when text doesn’t doesn’t change very frequently and there are many search queries. We have discussed Suffix Tree (A compressed Trie of all suffixes of Text) .

[ad type=”banner”]

Implementation of Suffix Tree may be time consuming for problems to be coded in a technical interview or programming contexts. In this post simple implementation of a Standard Trie of all Suffixes is discussed. The implementation is close to suffix tree, the only thing is, it’s a simple Trie instead of compressed Trie.

As discussed in Suffix Tree post, the idea is, every pattern that is present in text (or we can say every substring of text) must be a prefix of one of all possible suffixes. So if we build a Trie of all suffixes, we can find the pattern in O(m) time where m is pattern length.

Building a Trie of Suffixes
1) Generate all suffixes of given text.
2) Consider all suffixes as individual words and build a trie.

Let us consider an example text “banana\0” where ‘\0’ is string termination character. Following are all suffixes of “banana\0”

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

If we consider all of the above suffixes as individual words and build a Trie, we get following.

C Programming for Pattern Searching using a Trie of all Suffixes

How to search a pattern in the built Trie?
Following are steps to search a pattern in the built Trie.
1) Starting from the first character of the pattern and root of the Trie, do following for every character.
…..a) For the current character of pattern, if there is an edge from the current node, follow the edge.
…..b) If there is no edge, print “pattern doesn’t exist in text” and return.
2) If all characters of pattern have been processed, i.e., there is a path from root for characters of the given pattern, then print print all indexes where pattern is present. To store indexes, we use a list with every node that stores indexes of suffixes starting at the node.

[ad type=”banner”]

Following is C++ implementation of the above idea.

[pastacode lang=”c” manual=”%2F%2F%20A%20simple%20C%2B%2B%20implementation%20of%20substring%20search%20using%20trie%20of%20suffixes%0A%23include%3Ciostream%3E%0A%23include%3Clist%3E%0A%23define%20MAX_CHAR%20256%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20Suffix%20Trie%20(A%20Trie%20of%20all%20suffixes)%20Node%0Aclass%20SuffixTrieNode%0A%7B%0Aprivate%3A%0A%20%20%20%20SuffixTrieNode%20*children%5BMAX_CHAR%5D%3B%0A%20%20%20%20list%3Cint%3E%20*indexes%3B%0Apublic%3A%0A%20%20%20%20SuffixTrieNode()%20%2F%2F%20Constructor%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20an%20empty%20linked%20list%20for%20indexes%20of%0A%20%20%20%20%20%20%20%20%2F%2F%20suffixes%20starting%20from%20this%20node%0A%20%20%20%20%20%20%20%20indexes%20%3D%20new%20list%3Cint%3E%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20all%20child%20pointers%20as%20NULL%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20MAX_CHAR%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20children%5Bi%5D%20%3D%20NULL%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20to%20insert%20a%20suffix%20of%20the%20txt%0A%20%20%20%20%2F%2F%20in%20subtree%20rooted%20with%20this%20node%0A%20%20%20%20void%20insertSuffix(string%20suffix%2C%20int%20index)%3B%0A%20%0A%20%20%20%20%2F%2F%20A%20function%20to%20search%20a%20pattern%20in%20subtree%20rooted%0A%20%20%20%20%2F%2F%20with%20this%20node.The%20function%20returns%20pointer%20to%20a%20linked%0A%20%20%20%20%2F%2F%20list%20containing%20all%20indexes%20where%20pattern%20is%20present.%0A%20%20%20%20%2F%2F%20The%20returned%20indexes%20are%20indexes%20of%20last%20characters%0A%20%20%20%20%2F%2F%20of%20matched%20text.%0A%20%20%20%20list%3Cint%3E*%20search(string%20pat)%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20Trie%20of%20all%20suffixes%0Aclass%20SuffixTrie%0A%7B%0Aprivate%3A%0A%20%20%20%20SuffixTrieNode%20root%3B%0Apublic%3A%0A%20%20%20%20%2F%2F%20Constructor%20(Builds%20a%20trie%20of%20suffies%20of%20the%20given%20text)%0A%20%20%20%20SuffixTrie(string%20txt)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Consider%20all%20suffixes%20of%20given%20string%20and%20insert%0A%20%20%20%20%20%20%20%20%2F%2F%20them%20into%20the%20Suffix%20Trie%20using%20recursive%20function%0A%20%20%20%20%20%20%20%20%2F%2F%20insertSuffix()%20in%20SuffixTrieNode%20class%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20txt.length()%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20root.insertSuffix(txt.substr(i)%2C%20i)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20searches%20a%20pattern%20in%20this%20suffix%20trie.%0A%20%20%20%20void%20search(string%20pat)%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20recursive%20function%20to%20insert%20a%20suffix%20of%20the%20txt%20in%0A%2F%2F%20subtree%20rooted%20with%20this%20node%0Avoid%20SuffixTrieNode%3A%3AinsertSuffix(string%20s%2C%20int%20index)%0A%7B%0A%20%20%20%20%2F%2F%20Store%20index%20in%20linked%20list%0A%20%20%20%20indexes-%3Epush_front(index)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20string%20has%20more%20characters%0A%20%20%20%20if%20(s.length()%20%3E%200)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20the%20first%20character%0A%20%20%20%20%20%20%20%20char%20cIndex%20%3D%20s.at(0)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20there%20is%20no%20edge%20for%20this%20character%2C%20add%20a%20new%20edge%0A%20%20%20%20%20%20%20%20if%20(children%5BcIndex%5D%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20%20children%5BcIndex%5D%20%3D%20new%20SuffixTrieNode()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20next%20suffix%0A%20%20%20%20%20%20%20%20children%5BcIndex%5D-%3EinsertSuffix(s.substr(1)%2C%20index%2B1)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20function%20to%20search%20a%20pattern%20in%20subtree%20rooted%20with%0A%2F%2F%20this%20node%0Alist%3Cint%3E*%20SuffixTrieNode%3A%3Asearch(string%20s)%0A%7B%0A%20%20%20%20%2F%2F%20If%20all%20characters%20of%20pattern%20have%20been%20processed%2C%0A%20%20%20%20if%20(s.length()%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20indexes%3B%0A%20%0A%20%20%20%20%2F%2F%20if%20there%20is%20an%20edge%20from%20the%20current%20node%20of%20suffix%20trie%2C%0A%20%20%20%20%2F%2F%20follow%20the%20edge.%0A%20%20%20%20if%20(children%5Bs.at(0)%5D%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%20(children%5Bs.at(0)%5D)-%3Esearch(s.substr(1))%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20there%20is%20no%20edge%2C%20pattern%20doesn%E2%80%99t%20exist%20in%20text%0A%20%20%20%20else%20return%20NULL%3B%0A%7D%0A%20%0A%2F*%20Prints%20all%20occurrences%20of%20pat%20in%20the%20Suffix%20Trie%20S%20(built%20for%20text)*%2F%0Avoid%20SuffixTrie%3A%3Asearch(string%20pat)%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20call%20recursive%20search%20function%20for%20root%20of%20Trie.%0A%20%20%20%20%2F%2F%20We%20get%20a%20list%20of%20all%20indexes%20(where%20pat%20is%20present%20in%20text)%20in%0A%20%20%20%20%2F%2F%20variable%20’result’%0A%20%20%20%20list%3Cint%3E%20*result%20%3D%20root.search(pat)%3B%0A%20%0A%20%20%20%20%2F%2F%20Check%20if%20the%20list%20of%20indexes%20is%20empty%20or%20not%0A%20%20%20%20if%20(result%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Pattern%20not%20found%22%20%3C%3C%20endl%3B%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20list%3Cint%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20%20%20%20int%20patLen%20%3D%20pat.length()%3B%0A%20%20%20%20%20%20%20for%20(i%20%3D%20result-%3Ebegin()%3B%20i%20!%3D%20result-%3Eend()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Pattern%20found%20at%20position%20%22%20%3C%3C%20*i%20-%20patLen%3C%3C%20endl%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20build%20a%20suffix%20trie%20for%20text%20%22geeksforgeeks.org%22%0A%20%20%20%20string%20txt%20%3D%20%22geeksforgeeks.org%22%3B%0A%20%20%20%20SuffixTrie%20S(txt)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Search%20for%20’ee’%22%20%3C%3C%20endl%3B%0A%20%20%20%20S.search(%22ee%22)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnSearch%20for%20’geek’%22%20%3C%3C%20endl%3B%0A%20%20%20%20S.search(%22geek%22)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnSearch%20for%20’quiz’%22%20%3C%3C%20endl%3B%0A%20%20%20%20S.search(%22quiz%22)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnSearch%20for%20’forgeeks’%22%20%3C%3C%20endl%3B%0A%20%20%20%20S.search(%22forgeeks%22)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]

Output:

Search for 'ee'
Pattern found at position 9
Pattern found at position 1

Search for 'geek'
Pattern found at position 8
Pattern found at position 0

Search for 'quiz'
Pattern not found

Search for 'forgeeks'
Pattern found at position 5

Time Complexity of the above search function is O(m+k) where m is length of the pattern and k is the number of occurrences of pattern in text.

[ad type=”banner”]