Pattern searching by suffix tree

Question

The pattern searching in the given suffix tree takes O(m) time, where m is the length of the pattern. What about getting all the occurrences of the pattern in the text? I've read that if there are k occurrences of a pattern, then time complexity of finding them all in the text is O(m+k). But I am not able to understand this O(+k) time complexity. Any help!! [Definitely , pre -processing time is O(n): n being the length of the text].

Answer 1

The leaves below a node of the suffix tree store the suffix indices that begin with the prefix defined at the node. So you just need to count descendant leaves after you find the node for the match for your search pattern in the suffix tree. Using DFS this can be done in O(k) time for k leaves (k matches). If you just want to count how many occurrences there are, this can be done in constant time if you first use DFS to compute and store the number of leaves below each node as auxillary information at the node as additional preprocessing after you compute the suffix tree. (Still O(n) time).