1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Which formulation of the algorithm are you looking at? Give attribution! $\endgroup$ – Raphael Jul 12 '16 at 21:42
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.