Take the 2-minute tour ×

Based on this http://www.itu.dk/courses/AVA/E2005/StringIndexing.pdf on page 12/36

Given a string T[1...n], we build a suffix tree. The search pattern is P[1...m].

• Preprocessing: O(n^2)
• Space: O(n^2)
• Occur(P in suffix tree): O(n*m) <===== why?
• Member is: O(m)
share|improve this question
Where in that document does it say finding the occurrences is O(mn) time? From what I read it says it's O(m+z) where z is the number of occurrences. –  GWW Apr 14 '11 at 3:43
@GWW, on page 12. –  q0987 Apr 14 '11 at 14:48
add comment

1 Answer

up vote 1 down vote accepted

The Occur(...) operation in the material you refer to is not about searching for P from the suffix tree, but about finding longest matches (i.e. find the longest substring of P that occurs in the search tree) and report the corresponding leaves. It is worst case O(nm) operation because you need to take every suffix of P (that's O(m)) and possibly report O(n) leaves every time.

share|improve this answer
add comment

Your Answer


