Algorithms and Parallel Computing

15.2 EXPRESSING THE ALGORITHM AS A REGULAR ITERATIVE ALGORITHM (RIA)

To develop a multithreaded or systolic array implementation, we must first be able to describe the string matching algorithm using recursions that convert the algorithm into a RIA. We can write the basic string search algorithm as in Algorithm 15.1:

Algorithm 15.1

Basic string search algorithm

1: input T and P

2: for i = 0:n-m do

3: j = 0

4: while j < m AND t_i+j = p_j do

5: j = j + 1

6: end while

7: if j = m then

8: mathc_flag = TRUE

9: match_location = i

10: end if

11: end for

This algorithm can also be expressed in the form of an iteration using two indices, i and j:

(15.1)

where y_i is a Boolean-type output variable. If y_i = true, then there is a match at position t_i; that is, t_i:i+m+1 = p_0:m−1. Match(a, b) is a function that is true when character a matches character b. ∧ represents an m-input AND function.