pattern matching - KMP Table building algorithm -

i checked kmp table-building algorithm wikipedia don't understand logic behind second case of while loop

(second case: doesn't, can fall back)         else if cnd > 0             let cnd ← t[cnd] 

i tried build table using algorithm , works perfectly. understand cnd ← t[cnd] helps find proper suffix length. don't understand "how" it?

an explanation example nice.

thanks!

edit: found out question duplicate of question here: "partial match" table (aka "failure function") in kmp (on wikipedia)

i think answer now. still, 1 more explanation helpful. thanks!

suppose have string hello world!!! , want search head up.

hello world!!! head   ^ 

when in first , second character first condition apply (first case: substring continues), in case of marked position, character don't match inside sub-string match (2 character matched until there), case correspond second conditional (second case: doesn't, can fall back). third case when miss match first character of pattern.

the second condition necessary because use information of matched character until miss match, avoid unnecessary comparison known result (skip characters of string know beginning part of pattern don't match).

example: string hehello world!!! , searching hello

hehello world!!! hello   ^ when miss match character using table of kmp known      skip 2 characters because  hehello world!!!  hello  ^ miss match 

in case of building pattern table pattern hehello. suppose ^ cnd , * pos. start point pos = 2 , cnd = 0 (but when checking in pattern pos - 1 = 1).

hehehello     t [-1,0,0,0,0,0,0,0,0] ^* comparing 0 1 go condition 3        cnd = 0, pos = 2                         _ hehehello     t [-1,0,0,1,0,0,0,0,0] ^ * comparing 0 2 go condition 1       cnd = 0, pos = 3                           _ hehehello     t [-1,0,0,1,2,0,0,0,0]  ^ * comparing 1 3 go condition 1      cnd = 1, pos = 4                             _ hehehello     t [-1,0,0,1,2,3,0,0,0]   ^ * comparing 2 4 go condition 1     cnd = 2, pos = 5                               _ hehehello     t [-1,0,0,1,2,3,4,0,0]    ^ * comparing 3 5 go condition 1    cnd = 3, pos = 6  hehehello     t [-1,0,0,1,2,3,4,0,0]     ^ * comparing 4 6 go condition 2 (cnd = t[cnd], cnd = t[4] = 2)  hehehello     t [-1,0,0,1,2,3,4,0,0]   ^   * comparing 2 6 go condition 2 (cnd = t[cnd], cnd = t[2] = 0)  ...