内容介绍 解决问题:模式匹配,对应实际问题: Lecture11模式匹配 文本文件字符串查找 格式文件中的字符串及其格式查找问题 清华大学 算法: Naive, Rabin Karp,自动机 KMP,BM算法 宋斌恒 Figure 32. 1 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 3. The shifts=3 is said to be a valid shift. Each character of the Algorithm the text, and all matched characters are shown in green color rin pattern is connected by a vertical line to the matching charact Narve O((n-m+l)m) e(m) O(n-m+1)m) Finite automaton O(m2 text ababa bac Knuth Morris Pratt O(m) pattern P 8=3 H al bl al Terminology Lemma 32.1(Overlapping -sufix lemma) ·∑:字符集 ·∑:由Σ生成的所有字符串,包括空串的 Suppose that x, y, and z are strings such 集合以下叙述x,y,z,w表示其元素 that x ]z and y ]z If xs lyl, then x]y Concatenation of x, y: xy If x> lyl, then ]x If x= lyl, then x 前缀:[:w[x→ there exists y, such tha 后缀:]:wk→ there exists y, such that1 1 Lecture 11 模式匹配 清华大学 宋斌恒 2 内容介绍 • 解决问题：模式匹配，对应实际问题： – 文本文件字符串查找 – 格式文件中的字符串及其格式查找问题 • 算法：Naïve，Rabin Karp, 自动机， KMP，BM算法 3 Figure 32.1 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 pattern is connected by a vertical line to the matching character in the text, and all matched characters are shown in green color. text T pattern P b a b a a a c a b a a b c a b a c 4 本章算法及其复杂度列表 Algorithm preprocessing time matching time Naïve 0 O((n-m+1)m) Rabin-Karp Θ(m) O((n-m+1)m) Finite automaton O(m|Σ|) Θ(n) Knuth Morris Pratt O(m) Θ(n) BM 5 Terminology • Σ: 字符集 • Σ*:由Σ生成的所有字符串，包括空串的 集合,以下叙述x, y, z, w表示其元素 • Concatenation of x，y： xy • 前缀：[ : w [ x Î there exists y，such that x=wy • 后缀： ] : w ]x Î there exists y，such that x=yw 6 Lemma 32.1 (Overlapping-suffix lemma) Suppose that x, y, and z are strings such that x ] z and y ] z. If |x| ≤ |y|, then x] y. If |x| ≥ |y|, then y ] x. If |x| = |y|, then x = y