Cacher is the code snippet organizer for pro developers

# KMP with Examples
# Ex. abc abd abc abc
#     000 120 123 453 
# See hwo many letter do I have matched? & Who's next?

def kmp_matcher(text, pattern):
    pi = compute_prefix_function(pattern)
    matched = 0
    for i, char in enumerate(text):
        while matched > 0 and pattern[matched] != text[i]:
            matched = pi[matched - 1]
            matched += 1    
        if matched == len(pattern):
            return i - len(pattern) + 1
    return -1

def compute_prefix_function(pattern):
    pi = [0 for i in range(len(pattern))]
    matched = 0
    for i in range(1, len(pattern)):
        while matched > 0 and pattern[i] != pattern[matched]:
            matched = pi[matched - 1]
        if pattern[i] == pattern[matched]:
            matched += 1
        pi[i] = matched 
    return pi