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