The Analysis for KMP

KMP analysis

Assume target string: S0S1......Sn-1; pattern string: P0P1......Pm-1
So we have: StSt+1......St+j = P0P1......Pj, and St+j+1 != Pj+1

We should then compare St+1St+2......=P0P1......, However, if P0P1......Pj-1 != P1P2......Pj, then it must be failed!
We should then compare St+2St+3......=P0P1......, However, if P0P1......Pj-2 != P2P3......Pj, then it must be failed!

We only need find a k: P0P1......Pk=Pj-kPj-k+1......Pj AND P0P1......Pk+1 != Pj-k-1Pj-k......Pj

Because St+j-kSt+j-k+1......St+j=Pj-kPj-k+1......Pj=P0P1......Pk, So next time we only need to consider St+j+1 == Pk+1 ?

So we define F(j) = k, 0<=k<j, AND P0P1......Pk=Pj-kPj-k+1......Pj, the greatest integer
                  = -1, otherwise.
Note1: after getting k for F(j), S stay to St+j+1; and P don't go back to P0, instead, it only need to go back to Pk+1.

Note2: F(0) = -1, 1. because k cannot equal j; 2.if F(0) = 0, then F(1) must be 1, when comparing, infinite loop.
       Here F(x) x means xth char

Note3: Assume P0P1......Pk = Pj-kPj-k+1......Pj, f(j) = k, how to get f(j+1)?
1. if P(k+1) == P(j+1), then F(j+1) = k + 1
2. if not, then it must have F(j+1) <= F(j) = k, we are looking for h, (h < k)
   P0P1......Ph = Pj-hPj-h+1......Pj = Pk-hPk-h+1......Pk,
   So from above intuition, we can get: F(j+1) = f[x](j) + 1, if we can find the minimum x
                                        F(j+1) = -1, otherwise.