E D R S I H C RSS
ID
Password
Join
To laugh at men of sense is the privilege of fools.

FrontPage KMPAlgorithm

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)
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2013-05-06 01:17:25
Processing time 0.0120 sec