[prev] 16 [next]

Pattern Matching (cont)

Naive pattern matching algorithm
  • checks for each possible shift of P relative to T
    • until a match is found, or
    • all placements of the pattern have been tried 

NaiveMatching(T,P):
|  Input  text T of length n, pattern P of length m
|  Output starting index of a substring of T equal to P
|         -1 if no such substring exists
|
|  for all i=0..n-m do
|  |  j=0                            // check from left to right
|  |  while j<m and T[i+j]=P[j] do  // test ith shift of pattern
|  |  |  j=j+1
|  |  |  if j=m then
|  |  |     return i                 // entire pattern checked
|  |  |  end if
|  |  end while
|  end for
|  return -1                         // no match found