Knuth-Morris-Pratt Algorithm

                           ↓ never backup
    a b c x y z a b c d a b c d a b x y z
                a b c d a b x y
                   ↑      ↑
                Next[j]     j


     KMPsearch
       i = 1; j = 1;                                 a b c x y z
       repeat                                        x y z      next[1] = 0
         if j = 0 or a[i] = p[j] then                a b c x y z 
           i = i + 1; j = j + 1;                     a x y      next[2] = 1
         else                                        a b c x y z
           j = next[j];                              a b x y    next[3] = 1
       until j > M or i > N                          a a c x y z
              ↓       ↓                            a a x y    next[3] = 2
            i - M   Not Found


.How to compute next[j]?



     InitNext
       i = 1; j = 0; next[1] = 0;
       repeat
         if j = 0 or p[i] = p[j] then
           i = i + 1; j = j + 1; next[i] = j;
         else
           j = next[j];
       until i > M