42
Preprocessing Strings
(cont)
Reminder: A
trie
…
is a compact data structure for representing a set of strings
e.g. all the words in a text, a dictionary etc.
Tries support pattern matching queries in time
proportional
to the
pattern
size
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}