Boyer-Moore Algorithm
The Boyer-Moore pattern matching algorithm is based on two heuristics:
- Looking-glass heuristic: Compare P with subsequence of T moving backwards
- Character-jump heuristic: When a mismatch occurs at T[i]=
c
- if P contains
c ⇒ shift P so as to align the last occurrence of c in P with T[i]
- otherwise ⇒ shift P so as to align P[0] with T[i+1] (a.k.a. "big jump")
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}