
5.3 Matching Sequences of Real Numbers 139
occurrence of k in “bokks” has been changed to o. In addition, the vertical segment of the best path is
interpreted as the deletion of s in “bokks.” A total of one symbol change and one symbol deletion is
needed to convert “bokks” to “book” in an optimal way.
Similarly, the Edit cost for matching “teplatte” against “template” equals 2, and the resulting best
path can be seen in Figure 5.1(b). In this case, an insertion (horizontal segment) and a deletion (vertical
segment) are required to convert “teplatte” to the reference pattern in an optimal way.
Exercise 5.2.1
Given the words “impose,” “ignore,” and