CSC301.01 2015F, Class 39: Pause for Breath (Really String Matching)
====================================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Building prefix tables by hand.
* The Knuth-Morris-Pratt algorithm.
* An algorithm for building the KMP table.


Preliminaries
-------------

### Admin

* Weekly PSA.

### Upcoming Work

* [Exam 2](../assignments/exam.02.html): Due Friday, December 11th.

### Extra Credit

#### Academic

* Summer opportunities in CS, next Thursday at 4:15 p.m.

#### Peer

* Deshowber/Showcember, Friday, 8pm Gardner, SH at 8:30ish, YK at 12:00.

### Questions

_In problem 2, if we think that the heuristic is correct and want to
 argue that it's correct, can we discuss the steps of the algorithm?_

> Yes.

_For the dynamic programming text formatting problem, you don't describe
 the length of the individual words._

> Use length(word[i]) or length[i] or something similar.

_For the max jobs problem, what assumptions are we allowed to make?_

> Any one person can do only one job at a time.  Each person finishes
  a job before going on to the next job.  Each job requires only one
  person.

_What run time do you expect?_

> I'd like something better than "try every permutation".  Do the best
  you can.  Pretend it's Alphabet/7.

_What does the table in problem 1 look like?_

> Something like the following

<pre>
        c1      c2      c3      c4      c5      c6      ... cn
    s1  3       4       5       6       7       8
    s2  2.5     3       3.1     3.2     3.3     3.4
    s3  2.4     2.9     3.01    3.02    3.03    3.04
    s4  -9.5     -9      0       1       2       3
    s5  -9.6    -9.1    -2      0       1       2
    .
    .
    .
    sn
</pre>

Prefix Tables, Revisited
------------------------

We have decided that we can do pattern matching more efficiently if
we have a table that tells us how much of the pattern we can still
note that we've matched when we hit a non-matching character.

Example

    pattern: a a a a b
    preserve:0 0 0 0 3

Pictorially

    text: a a a a a a a c a a a a a b
          a a a a FAIL
            a a a a FAIL
              a a a a FAIL
                a a a a FAIL
                  a a a FAIL
                        FAIL
                          a a a a FAIL
                            a a a a b DONE

Two important issues

* Some failures advance the pattern significantly (e.g., failure at c)
* Although we show ourselves restarting, we only have to look at the 
  "current character"

Hand wave:

* If we have the table, this is an O(n) algorithm- We look at each
  character in the string no more than twice.

We decided we should try to build our own tables.

    pattern: a b a b a c
    preserve:0 0 0 1 2 3

An attempt at matching

    text: a b a b a b a c
          a b a b a c
                    FAIL
              a b a b a c DONE

    text: a b a c a b a c c
          a b a b a c
                FAIL
              a b a b a c
                FAIL
                a b a b a c
                FAIL
                  a b a b a c
                  OUT OF TEXT

A better table

    pattern: a b a b a c
    preserve:0 0 0 0 0 3

Another example

    pattern: a b a c a b
    preserve:0 0 0 1 0 0

    pattern: a b c a b c c a b d
    preserve:

    pattern: a b c a b c a c a b  (from KMP)
    preserve: 

The Knuth-Morris-Pratt Algorithm
--------------------------------

    Inputs:
      text, a string
      pattern, a string
      P, the table described above
    Steps:     
      i = 0; // Index into text
      j = 0; // Index into pattern
      while (i < length(text) - length(pattern))
        if (j == length(pattern))
          return MATCH at i-j.
        else if (text[i] == pattern[j])
          ++i;
          ++j;
        else if j == 0
          ++i
        else
          j = P[j]


Building the KNP Table
----------------------

Ideas?