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 ti+j = pj 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:
where yi is a Boolean-type output variable. If yi = true, then there is a match at position ti; that is, ti:i+m+1 = p0:m−1. Match(a, b) is a function that is true when character a matches character b. ∧ represents an m-input AND function.