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.
At first you need to identify the idea of proper-prefix and proper-suffix.
s-suffix p-prefix pp-proper prefix ps-proper suffix PT-pattern |s| <= |PT| |p| <= |PT| |pp| < |PT| |ps| < |PT|
proper suffix is a string that is not equal to string itself.
In the KMP algorithm we need to identify longest prefix of p that is also proper suffix of p. So we can't take whole pattern as a proper-prefix or proper-suffix.So for a single character there is not exist proper-prefix or proper-suffix.Then sp value of the first element has to be 0.