几乎每天都在用。。 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几乎每天都在用