algorithm - Understanding the Knuth Morris Pratt(KMP) Failure Function -

algorithm - Understanding the Knuth Morris Pratt(KMP) Failure Function -

i've been reading wikipedia article knuth-morris-pratt algorithm , i'm confused how values found in jump/partial match table.

| 0 1 2 3 4 5 6 w[i] | b c d b d t[i] | -1 0 0 0 0 1 2

if can more explain shortcut rule because sentence

"let discovered proper suffix proper prefix , ending @ w[2] length 2 (the maximum possible)"

is confusing. if proper suffix ends @ w[2] wouldn't size of 3?

also i'm wondering why t[4] isn't 1 when there prefix , suffix of size 1: a.

thanks help can offered.

notice failure function t[i] not utilize index, rather length. therefore, t[2] represents length of longest proper border (a string both prefix , suffix) of string formed first 2 characters of w, rather longest proper border formed string ending @ character 2. why maximum possible value of t[2] 2 rather 3 - substring formed first 2 characters of w can't have length greater 2.

using interpretation, it's easier see why t[4] 0 rather 1. substring of w formed first 4 characters of w abcd, has no proper prefix proper suffix.

hope helps!

algorithm string-matching knuth-morris-pratt