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