计算机问题求解-论题4-5 。串匹配 2019年3月27日
计算机问题求解 – 论题4-5 - 串匹配 2019年3月27日
问题1： 什么是string-matching problem,直观上？形式上？
string-matching problem
几乎每天都在用。。 Introduction to Algorithms,Third Edition 1007/1313 Knuth-Morris-Pratt 1/2 Tigure 32.2 The strmg-matehing aigonmms m ts cnaprer and men preprocessig and matcmng times. Except for the naive brute-force algorithm.which we review in Section 32.1. each string-matching algorithm in this chapter performs some preprocessing based on the pattern and then finds all valid shifts;we call this latter phase"matching." Figure 32.2 shows the preprocessing and matching times for each of the algorithms in this chapter.The total running time of each algorithm is the sum of the prepro- cessing and matching times.Section 32.2 presents an interesting string-matching algorithm.due to Rabin and Karp.Although the ((n-m +1)m)worst-case running time of this algorithm is no better than that of the naive method,it works much better on average and in practice.It also generalizes nicely to other pattern- matching problems.Section 32.3 then describes a string-matching algorithm that begins by constructing a finite automaton specifically designed to search for occur- rences of the given pattern P in a text.This algorithm takes O(m preprocess- ing time,but only (n)matching time.Section 32.4 presents the similar,but much cleverer.Knuth-Morris-Pratt (or KMP)algorithm:it has the same (n)matching time,and it reduces the preprocessing time to only (m). 出 Notation and terminology We denote by E*(read"sigma-star")the set of all finite-length strings formed using characters from the alphabet In this chapter,we consider only finite- length strings.The zero-length empty string,denoted 8,also belongs to 'The
几乎每天都在用
text T a b c ab a a b a b a 5=3 a a we say that pattern P occurs with shift s in text T (or,equivalently,that pattern P occurs beginning at position s+1 in text T)if 0≤s≤n-m and T5+l.s+m=P[l.m(that is,.ifT5+j】=P[Ujl,for 1 j<m).If P occurs with shift s in T,then we call s a valid shift;otherwise, we call s an invalid shift.The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T
text T a b a b a a b a b a 5=3 pattern P b a a Worst Case Algorithm Preprocessing time Matching time Naive 0 O((n-m+1)m) Rabin-Karp ⊙(m) O(n-m+1)m)） Finite automaton O(m∑) ⊙(n) Knuth-Morris-Pratt ⊙(m) Θ(n) n:the length of text T m:the length of pattern the alphabet set,consisiting ofall possible characters
𝑛:𝑡ℎ𝑒 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑡𝑒𝑥𝑡 𝑇 𝑚:𝑡ℎ𝑒 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑝𝑎𝑡𝑡𝑒𝑟𝑛 𝛴:the alphabet set , consisiting of all possible characters Worst Case