Analysis of Algorithms : An Active Learning Approach

5.1 STRING MATCHING 123

In the first case we are done, but in the second, we move the starting point in

the text by one character and begin matching with the substring again. This

process can be seen in Fig. 5.1.

The following algorithm accomplishes this standard string match:

subLoc = 1 // current match point in substring

textLoc = 1 // current match point in text

textStart = 1 // location where this match attempt starts

while textLoc ≤ length(text) and subLoc ≤ length(substring) do

if text[ textLoc ] = substring[ subLoc ] then

textLoc = textLoc + 1

subLoc = subLoc + 1

else

// begin again but move the start by 1

textStart = textStart + 1

textLoc = textStart

subLoc = 1

end if

end while

■FIGURE 5.1
Match of substring
“they” in text “there
they are.” The first
pass matches
three characters of
the substring, but
only the seventh
pass matches
completely. (There
are 13 character
comparisons done
to find the match.)

Text: there they are

Pass 1: they

Text: there they are

Pass 2: they

Text: there they are

Pass 3: they

Text: there they are

Pass 4: they

Text: there they are

Pass 5: they

Text: there they are

Pass 6: they

Text: there they are

Pass 7: they