String Matching

.Brute-force

                         i - j + 2    i
                                    
Text     a[N]: a b c x y z a b c d a b c d a b c x y z
Pattern  p[N]:             a b c d a b x y
                                      
                                      j

BruteSearch i = 1; j = 1; repeat if a[i] = p[j] then i = i + 1; j = j + 1; else i = i - j + 2; j = 1; until j > M or i > N i - M Not Found
Too bad! . 0 0 0 0 0 0 0 0 0 0 0 0 1 8 * 5 + 5 0 0 0 0 1 . 1 0 0 0 0 0 0 0 0 0 0 0 0 => Boyer-Moore 1 0 0 0 0 0 T = MN