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