prefix_function.py

def prefix_function(s):
    result = len(s) * [0]

    for (i, c) in enumerate(s):
        if i == 0:
            continue

        guess = result[i - 1]

        while True:
            if s[guess] == c:
                result[i] = guess + 1
                break
            elif guess == 0:
                break
            else:
                guess = result[guess]

    return result

def search_using_prefix(needle, haystack):
    matches = []
    s = needle + '$' + haystack
    p = prefix_function(s)
    for (i, _) in enumerate(haystack):
        j = i + len(needle) + 1
        if p[j] == len(needle):
            matches.append(i - len(needle) + 1)

    # Debug output:
    for match in matches:
        print(haystack[match:match+len(needle)])

    return matches

def main():
    print(prefix_function('abacabadaba'))
    print(search_using_prefix('long', 'long cat is very long'))

if __name__ == "__main__":
    main()