57
Pattern Matching With Suffix Tries
(cont)
Analysis of pattern matching using suffix tries:
Suffix trie for a text of size
n
…
can be constructed in
O(n)
time
uses
O(n)
space
supports pattern matching queries in
O(m)
time
m
… length of the pattern
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}