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 // end if
  9.     else
  10.       index <- index + 1 // end else
  11.     if match then
  12.       write position // end if & end inner until
  13.   position <- position + 1 // end outer until
  14. stop

Worst case: O(mn)

Best case: O(n)

Average case: O(n) under reasonable assumptions for a random pattern and random text.

QUESTION: If the pattern length (m) is longer than the string length (n) what will happen in the above algorithm?


[Prev][TOC][Next]

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