The KMP Algorithm implementation in Python

kmp_alg

def buildPMT(s):
    """
    PartialMatchTable of string s
    """
    prefix = [s[:i+1] for i in range(len(s)-1)]
    postfix = [s[i+1:] for i in range(len(s)-1)]
    intersection = list(set(prefix) & set(postfix))
    if intersection:
        return len(intersection[0])
    return 0
    
def kmp(src,target):
    i = 0
    while i < len(src) - len(target) + 1:
        match = True
        for j in xrange(len(target)):
            if src[i+j] != target[j]: 
                match = False
                break
        if match:
            return True
        # j is the unmatched postion in target
        if j:
            i += j - buildPMT(target[:j]) #move to the postion by i and compared string's length of target
        else:
            i += 1
    return False