
def kmp(text, pattern):
    pattern = list(pattern)

    #Partial match" table
    t = kmp_partial_match_table(pattern)

def kmp_shift_table(pattern):
    shifts = [None] * (len(pattern) + 1)
    shift = 1

    for pos in range(len(pattern) + 1):
        while shift < pos and pattern[pos - 1] != pattern[pos - shift - 1]:
            shift += shifts[pos - shift - 1]
        shifts[pos] = shift
    return shifts


def kmp_partial_match_table(pattern):
    N = len(pattern)
    l = 0 #length of the previous longest prefix suffix
    lps = [0] * len(pattern)
    i = 1
    while i < N:
        print i,l
        if pattern[i] == pattern[l]:
            l +=1
            lps[i] = l
            i += 1
        else:
            if l != 0:
                l = lps[l - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_first_match(text, pattern):
    shifts = kmp_shift_table(pattern)

    start_pos = 0
    match_len = 0
    for c in text:
        while match_len >=0 and pattern[match_len] != c:
            start_pos += shifts[match_len]
            match_len -= shifts[match_len]
        match_len +=1

        if match_len == len(pattern):
            return start_pos
    return False



if __name__ == '__main__':
    t = "BBC ABCDAB ABCDABCDABDE"
    p = "ABCDABD"
    # p = "AABAAAB"
    # p = "AABAACAABAA"
    # kmp(t, p)
    print kmp_partial_match_table(p)
    print kmp_shift_table(p)
    print kmp_first_match(t, p)

@@ -1229,16 +1229,465 @@
  False%0A%0A
+def kmp_all_matches(text, pattern):%0A    shfits = kmp_shift_table(pattern)%0A    start_pos = 0%0A    match_len = 0%0A%0A    for c in text:%0A        while match_len %3E= 0 and pattern%5Bmatch_len%5D != c:%0A            start_pos += shfits%5Bmatch_len%5D%0A            match_len -= shfits%5Bmatch_len%5D%0A        match_len += 1%0A        if match_len == len(pattern):%0A            yield start_pos%0A            start_pos += shfits%5Bmatch_len%5D%0A            match_len -= shfits%5Bmatch_len%5D%0A
 %0A%0Aif __n

update KMP algorithms to supports match all feature