算法分析与设计2005春.课件.第11讲.pdf

内容介绍
•解决问题:模式匹配,对应实际问题:
Lecture 11 模式匹配–文本文件字符串查找
–格式文件中的字符串及其格式查找问题
•算法:Naïve,Rabin Karp, 自动机,
清华大学 KMP,BM算法
宋斌恒
1 2
Figure The string-matching problem. The goal is to 本章算法及其复杂度列表
find all occurrences of the pattern P = abaa in the text T =
abcabaabcabac. The pattern occurs only once in the text, at shift s
= 3. The shift s = 3 is said to be a valid shift. Each character of the Algorithm preprocessing time matching time
pattern is connected by a vertical line to the matching character in
Naïve 0 O((n-m+1)m)
the text, and all matched characters are shown in green color.
Rabin-Karp Θ(m) O((n-m+1)m)
Finite automaton O(m|Σ|) Θ(n)
text T a b c a b a a b c a b a c Knuth Morris Pratt O(m) Θ(n)
BM
pattern P a b a a
3 4
Terminology
Lemma (Overlapping-suffix lemma)
字符集
•Σ: Suppose that x, y, and z are strings such
*
•Σ:由Σ生成的所有字符串,包括空串的≤
集合,以下叙述x, y, z, w表示其元素 that x ] z and y ] z. If |x| |y|, then x] y.
≥
• Concatenation of x,y: xy If |x| |y|, then y ] x. If |x| = |y|, then x
•前缀:[: w [ x Î there exists y,such that = y.
x=wy
•后缀: ] : w ]x Î there exists y,such that
x=yw
5 6
1
Figure A graphical proof of Lemma . We suppose that x ] a and y ] z.
The three parts of the figure illustrate the three cases of the lemma. Vertical lines
connect matching regions (shown shaded) of the strings. (a) If