Coding/Python 삽질기2013. 5. 6. 00:43

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)






'Coding > Python 삽질기' 카테고리의 다른 글

fibonacci 수열  (0) 2013.06.20
10000개의 겹치는 않는 좌표 만들기  (0) 2012.11.07
[Python] Undo / Redo 구현하기  (0) 2011.06.16
Posted by chobocho