Why do we take value from the already constructed array in KMP algorithmn when moving back when there is a mismatch , instead of starting from first?

Question

Why do we take value from the already constructed array in KMP algorithm when moving back (when there is a mismatch), instead of starting from first? Also how does it guarantee from that point before, the values are fine?

eg :

id = 0 1 2 3 4 5 6 7 8
s =  a a b a a b a a a
arr  0 1 0 1 2 3 4 5 2  

Considering i = 0 and j = 1, we start the algorithm.

Why do we have a condition of moving:

i > 0 and charAt(i) != charAt(j) then i = arr[i-1]

How exactly does this line in KMP work?

Answer 1

arr was built specifically to take advantage of what you have already previously matched to get a head start once a mismatch occurs.

For example: suppose you have matched aabaa, but the next character isn't the expected b, but an a. This means what we have processed so far ends with aa, which is why arr[i-1] is 2: the position where we've matched the aa at the start of string we're looking for.