Algorithms



Final Refined Pattern Matching Algorithm

  1. read n, m, T1, T2, ..., Tn, P1, P2, ..., Pm

  2. position <- 1

  3. repeat until position > n - m + 1

  4.      index <- 1

  5.      match <- true

  6.      repeat until either index > m or not match

  7.           if Pindex != Tposition+index-1 then

  8.                  match <- false

  9.           else

  10.               index <- index+1 (end inner until)

  11.    if match then

  12.        write position

  13.    position <- position +1 (end outer until)

  14. stop


Result is two nested loops. Identify them.

How is this algorithm an example of divide and conquer?

[Prev][TOC][Next]


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000