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: 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

        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

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?