CSC301.01 2015F, Class 38: Improved String-Matching Algorithms
==============================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Matching Multiple Strings.
* Analysis.
* Other Approaches to Matching Single Strings.
* Knuth-Morris-Pratt, Introduced.

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

### Admin

### Upcoming Work

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

### Extra Credit

#### Academic

* _Campus Town Hall on Student Well-Being_, 7:30 p.m. on Wednesday,
  December 2 in JRC 101.  TODAY!
* Future of the Libraries Talk, December 3, Noon, JRC 101.
  TOMORROW!
* _Human Computers at NASA_, 8 p.m., December 3, ARH 302
  TOMORROW!
* CS Extras, Thursday, Summer Research at UMich, 4:15 p.m. 3821.
  TOMORROW!

#### Peer

* Deshowber/Showcember, Friday, 8pm Gardner.

### Questions

* Done.

Matching Multiple Strings
-------------------------

* Given a text, t, of length n, and k patterns of length m, find the
  index of each pattern in t.
* Solution: "Hash functions"
    * Compute the hash value of each pattern
    * Compute the hash value of each position in the text
    * Iterate through the text, looking at the current hash value.
      If it matches one of the pattern hashes, check to make sure
      that they match.  If so, report a match at that position.
* Problem: O(m) to hash at each position for an arbitrary hash function.
* That makes our algorithm O(mn) for the hashing of the text, O(km) for
  the hashing of the patterns, and some amount of work for the comparisons
  when the hash codes match.

### Improved Hashing

* A good hash function can reduce the cost of making the hash codes in
  the text to O(n).
* We can use Skiena's hash function (really Rabin-Karp).
    * To hash c[1]...c[m], you compute the sum:
      c[1]*alpha^1 + c[2]*alpha^2 + c[3]*alpha^3 + ... + c[m]*alpha^m,
      where alpha is the alphabet size.
    * We can them compute the hash of c[2] ... c[m+1] by
      subtracting c[1]*alpha^1, divide by alpha, giving
      c[2]*alpha^1 + c[3]*alpha^2 ... c[m]*alpha^(m-1).  Then add
      c[m+1]*alpha^m.
    * What if our hash function is c[1]*alpha^(m-1) + c[2]*alpha^(m-2) +
      c[3]*alpha^(m-3) + ... c[m]*alpha^0?
    * We can compute the hash of c[2]...c[m+1]?  Subtract c[1]*alpha^[n-1],
      multiply by alpha, add c[m+1].
    * The latter is likely to be easier (multiplication is easier than
      division).

### Analysis

* Suppose k is 1.  What's the asymptotic running time?
* Compute all of the hash codes for the text.  O(n)
* Compute the hash code for the pattern.  O(m)
* Look at each position.  If the hash codes match, check if the pattern
  matches the text.  O(m)
* Since we might have a matched hash code at each position, there is
  O(m) work per position and O(n) positions, so this is O(mn).

### What if the Strings are not the same length?

* Note: We've simplified the problem by making all of the patterns the
  same length.  

Other Approaches to Matching Single Strings
-------------------------------------------

We would hope that we can do better.

* Suppose the pattern is a a a b.
* The text is 
  * b (have a a a b left)
  * a (still have a a b left)
  * a (still have a b left)
  * a (still have b left)
  * a (whoops!  Didn't match; If we are smart, we observe that we've
       still matched a a a, so only have b left)
  * c (whoops!  Didn't match.  Need to start over.)

We want a table that tells us how many characters from the pattern
still match when we fail to match at a particular character.

Pattern / Characters you can keep

        a a a b
        0 0 0 2

        a b a c

        a b a b a c
        0

Think about this for FRIDAY!
              
Knuth-Morris-Pratt, Introduced
------------------------------