KMP algorithm

def KMP_Preprocessing(pattern, nSize):

    pi = [0] * (nSize + 1)

    k = -1

    j = 0

    pi[j] = k

    

    while ( j < nSize ):

        if ( k == -1 or pattern[j] == pattern[k] ):

            j += 1

            k += 1

            pi[j] = k

        else:

            k = pi[k]

            

    return pi

def KMP_find(text, pattern, ppi):

    nSize = len(text)

    nPSize = len(pattern)

    i = 0

    j = 0

    while (i < nSize):

        if ( j == -1 or text[i] == pattern[j] ): 

            i += 1

            j += 1

        else:    

            j = ppi[j];

        if (j == nPSize):

            print i-j

            j = ppi[j];

strPattern = "ababababca"

strPattern_pi = KMP_Preprocessing(strPattern, len(strPattern) )

strString ="asdsadf9alkjababababcaasdf"

KMP_find(strString, strPattern, strPattern_pi)