Held: Wednesday, 2 December 2015

Back to Outline 37 - String Matching Basics. On to Outline 39 - Pause for Breath.

Summary

We continue our exploration of string matching.

Related Pages

Overview

• Matching Multiple Strings.
• Other Approaches to Matching Single Strings.
• Knuth-Morris-Pratt, Introduced.

Administrivia

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, 9pm Gardner.

Matching multiple strings

• What algorithms do you know for matching multiple substrings (e.g., finding each position of each substring)?
• What's the running time?
  • text is length n.
  • There are k patterns, each of length m.
• One algorithm we know is Rabin-Karp, which we discussed during our discussion of hashing..

Substring matching, revisited

• Can we write a single substring matching algorithm that reads each character in the text at most once, perhaps by doing some preprocessing of the pattern string?
• Why? Perhaps we have a limited buffer and we're reading from somewhertext else? Perhaps because we know that sensible use of the i
• Example 1
  • pattern: aaab
  • text: aaaaaaab
• Example 2
  • pattern: abcabcabd
  • text: abcabcabcabdbc
• Example 3 (due to Knuth, Morris, Pratt)
  • pattern: abcabcacab
  • text: babcabcabcaabcabcabcacabc
• We should find that we'll end up with a model of "re-placing" the pattern.