CSC301.01 2015F, Class 37: String Matching Basics
=================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Variant of string matching.
* Approximate string matching, revisited.
* Multiple string matching.
* Substring matching.

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

### Admin

* Welcome back!  I hope you had a great break.
* Food!  (At least a little.)
* News.

### Upcoming Work

* [Exam 2](../assignments/exam.02.html): Due Friday of Week 14.

### Extra Credit

#### Academic

#### Peer

* 1/40 of Deshowber.  Friday at 8ish at Gardner.

### Questions

_Do we need to write working code for the exam?_

> Pseudocode is fine.  But working code is also fine, provided it's
  not in ML or a variant thereof.

_Do we need to write a program to make the Huffman tree?_

> No.  Construct it by hand.  (If you want to write a program, that's
  fine, but it will be faster to construct by hand.)

_When is the final?_

2 p.m., Tuesday of Finals week (15th, I think).  In-class.  One sheet of
notes.

Variants of string matching
---------------------------

String matching: Given a target string and a pattern string, find where
the pattern string appears in the target string.

* Example: 
  Target: The College aims to graduate students of good character who
          can do good in the world.
  Pattern: good
  Solution: 40, 62 (those were approximated)

Variation one: Do we match exactly or approximately?

Variation two: Given a set of patterns, where does each pattern occur?

Variation three: What is the *first* occurrence vs. what is *any* occurrence
vs. What are *all* occurrences?

Approximate string matching, revisited
--------------------------------------

How would you change the dynamic programming approximate string matching 
algorithm to find the first matching substring that requires no more than
3 edits?

E.g., If we had a target string of "alphabet" and a pattern of "habit",
we can match at position 3 with two edits (one insertion of i, one deletion
of e, or vice versa) or with one edit if we allow replacement (replace
e with i).

Solution: Use the dynamic programming approximate string matching algorithm,
but it costs 0 to delete at the front of the string.

Multiple string matching
------------------------

Given k strings of length m, find all occurrences of each of the strings
in the target, which is of length n.

Analyze.  Here's a really bad input

target: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad
patterns aaaaaaaaaaaaaaaaaab
         aaaaaaaaaaaaaaaaaac
         aaaaaaaaaaaaaaaaaad
         aaaaaaaaaaaaaaaaaae
         aaaaaaaaaaaaaaaaaaf

Hint: We studied this once before.  DON'T USE DYNAMIC PROGRAMMING.  

An obvious solution

    for i = 0; i < (n - m)
      for j = 0, j < k; j++
        if (pattern[j] == substring(str, i, m))
          output "pattern[j] matches at position i"

Analysis?

* Concise.  Understandable.  O(n*m*k).  If k is 1,
  and the pattern is short, this is O(n).  We can't do much better than
  O(n).
* But the constant multipliers are important in practice.
* Trick!  Compute the hash code of each of the pattern strings.
  O(k*m) to compute.
* Compute the hash code at each position in the target.  O(n*m)
* Total: O(k*m + n*m)
* If you use a clever hash function, you can compute the hash code at
  position i from the hash code at position i-1 in a constant number
  of steps.  Total O(k*m + n).
* For next class, be prepared to describe a hash function that has this
  characteristic.

Substring matching
------------------