Why is fail[1] in KMP Algorithm always 0? I'm studying KMP Algorithm. In the failure function (or the sp table), why do we always assign the value 0 to the first element (character) of the pattern? I understand about the later elements of the pattern, as we assign the sp values according to length of correctly matched suffixes and prefixes, but why does the sp value of the first element has to be 0?
This is by definition, since:


  For each position i in pattern P, spi is defined as the length of longest proper suffix of P[1...i] that matches a prefix of P.


So, we can conclude that for i=1 the length of longest proper suffix that matches the prefix is 0 since longest prefix = suffix = EMPTY_STRING.

Visit this page for details.