On KMP

Note I find Robin-Karp rolling hash is way more likely to use than KMP since it is easier to code

Partial Match Table Example

W = "ABCDABD"

T[0] Special case => -1

T[1] no proper suffix exists, so match length = 0 => 0

T[2] B != A, since we are at i = 0 already, we can not relax further => 0

T[3] C != A, argument similar to T[2] => 0

T[4] D != A, arugment similar to T[2] => 0

T[5] A = A, so T[5] = 1, next we need to try match i = 1

T[6] B = B, so T[6] = T[5] + 1 = 2, next we need to try match i = 2

T[7] => no, we have reached the end! But let us try it out regardless, i.e., assume there is more letters after index 6

So D != C, i.e., not possible to form prefix ABC! so we need to try to form a shorter prefix. However, notice that we miss only the last char C, and AB already matches.

What the longest proper suffix of AB that is also a prefix of AB? We already have that prefix matched, so we have to try it out, since it could be a potential match/

length longest proper suffix of AB that is also a prefix of AB = T[2] = 0 = next i try to match against D.

Note that it D = A and we are at i =0 already, D[7] will be 0