1. Suppose you are given as input a string s of 0's and 1's, and you
wish to determine all strings w such that w0 and w1 are both contiguous
substrings of s. Describe how to do this efficiently using a suffix tree.
Note that each w can be output in constant time by listing a start
position in s and a length, so you do not need to worry about the amount
of time needed to output the actual strings.

For instance, if s consists of n-1 0's followed by a single 1, then the
strings w that should be output are the empty string, 0, 00, 000,
... up to n-2 0's.  These can all be specified as starting at position 0
in s and continuing for all possible lengths from 0 to n-2.


2. How much time would a flat tree take per operation (using O-notation)
on inputs consisting of sets of integers in the range from 0 to (sqrt n)!
(that's the factorial of sqrt n)? Use the approximation log x! ~= x log x.


3. Suppose we want to maintain a set of integers, stored as machine
words with W bits per word, and answer range counting queries that ask
for the number of stored integers within some interval. Can we do this
efficiently using a flat tree? What would be the time per operation?