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: 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(nmk). 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(km + nm)
• 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