You should be able to answer each of the following questions.
- Can you prepare a table for all of the operations discussed
in regard to PAT searching, showing the computational complexity?
- If the skipped bits were not skipped, what effect would
that have on the size of a PAT tree?
- For what operations would keeping the size of the
associated subtree, for each internal node, be useful?
- Is the ``delayed reading paradigm'' a type of ``lazy
evaluation'' scheme?
- Why are the results in Figures 10.7 and 10.11 different?
- Why is the ``match heuristic'' of Boyer-Moore not as valuable
as one might think?
- What methods for string searching work well when the pattern
has ``don't care'' symbols?
- What methods are likely to be used in the grep family
of UNIX commands, and why?