Today I'll introduce the hw5 program part: BWT.java
I already talked about BWT in general last time.

This will be your last program assignment, due Thursday next week.  I
also expect to give you a hw5 written part, but it will be due a
little later (near the last meeting).

I'll review the elements in BWT.java, but expect you to read
hw5/Notes.txt for the main ideas.

Then we'll go on to string matching, from Section 5.3.
We may not look at the entire section, but we at least
want to compare these two:

    Brute.java   -- brute force approach (hulk smash...)
    KMP.java     -- Knuth-Morris-Pratt algorithm (linear)

See: 5.3 slides and KMP movie (today's directory)

The nice observation of KMP is that there is a DFA (a deterministic
finite automaton) which can solve the string matching problem, while
reading each symbol of the input exactly once.  Simulating a DFA is
easy, but the challenge is finding this DFA.

Maybe also KMPplus.java, an improved version of the algorithm which
using space O(M) rather than O(MR).  They describe it in terms of an
NFA.  The key idea is the following:
  For each j, let P = pattern.substring(0,j) (first j symbols).
  Compute next[j] = the length of the longest proper suffix
  of P which is also a prefix of P.
  Then jumping from j to next[j] corresponds to the
  unlabeled back arrows in their NFA diagram.