Analysis of Algorithms : An Active Learning Approach

134 MATCHING ALGORITHMS

test = test - 1
target = target - 1
end while

for i = 1 to target do
jump[ i ] = MINIMUM( jump[ i ], length(pattern) + target - i )
end for

temp = link[ target ]
while target ≤ length(pattern) do
while target ≤ temp do
jump[target] = MINIMUM(jump[target], temp-target+length(pattern))
target = target + 1
end while
temp = link[temp]
end while

Figure 5.8 shows the values of the jump and link arrays after each of the

loops for the pattern value “datadata.”

15 14 13 12 11 10 9 8

56787889

15 14 13 12 11 10 3 1

11 10 9 8 11 10 3 1

11 10 9 8 11 10 3 1

Second loop

First loop

Fourth loop

link

jump

jump

Third loop

jump

jump

■FIGURE 5.8

Calculation of the

jump array for

“datadata”