Analysis of Algorithms : An Active Learning Approach

5.1 STRING MATCHING 131

character of the pattern as shown in Fig. 5.6(b). Then we begin the matching

process from the right end again. To do this, we need to reset patternLoc to

be the size of the pattern, and textLoc has to be increased by 4, which is

what really moves the pattern.

To accomplish this method of movement, we therefore need to determine

how much to increase textLoc based on the character that didn’t match. We

will use an array called slide that is as large as the character set that can

appear in the text. We initialize each element of the slide array to the size of

the pattern, because any characters not in the pattern should move the pattern

that amount. We then update the values for each character that does appear. If

a character appears more than once, the slide value will move the pattern so

the alignment is with the last occurrence. Alignment with characters earlier in

the pattern would be done by the jump factor, which will be discussed next.

The algorithm to calculate the slide values is

for every ch in the character set do

slide[ ch ] = length(pattern)

end for

for i = 1 to length(pattern) do

slide[ pattern[i] ] = length(pattern) - i

end for

textLoc

Text: baabacacbacb

Pattern: abacac

patternLoc

(a)

textLoc

Text: baabacacbacb

Pattern: abacac

patternLoc

(b)

↓

↓

↑

■FIGURE 5.6 ↑
Deciding on a
slide value