To find a word in a line of text, begin at the first character and ask whether the whole word fits there. Then move one position along and ask again. A search algorithm repeats this small test until the word can no longer fit before the text ends. section 4.2
The procedure uses a position in text, pt, starting at 0. While pt plus the word length is no greater than the text length, it calls compare at that position. A successful comparison prints pt; then search calls itself with pt + 1. This checks overlapping possible starting places as well as obvious ones. section 4.2
Finding “horses”
With “horses” as the word and “houses and horses and hearses” as the text, the search tries each legal starting position. The comparison function advances through matching character pairs and returns true only after reaching the word’s length; a differing character returns false. section 4.2
Listing 4.9 The whole program
1 define compare pt pw 2 if pw = length W then return true 3 if T[pt] = W[pw] then compare (pt + 1) (pw + 1) 4 return false 5 6 define search pt 7 if pt + length W <= length T then 8 if compare pt 0 then print pt 9 search (pt + 1)
The complete pseudocode places the boundary check, comparison, printing, and move to the next position side by side. section 4.2
