Algorithms


Refined Pattern Matching Algorithm

Adding details for the representation of the pattern and the text, we obtain:

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

  2. position <- 1

  3. repeat until position > n - m + 1

  4.     if P1P2... Pm occurs at position in T1T2... Tn then

  5.         write position

  6.     position <- position + 1

  7. stop

we still need to refine the check in step 4:

if P1P2... Pm occurs at position in T1T2... Tn

[Prev][TOC][Next]


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