Princeton KMP implementation
A few things pop out:


this:

needle_dict = dict(zip(list(set(needle).union(set(haystack))), range(len(list(set(needle).union(set(haystack)))))))



...creates two identical sets.  More space(and time, perhaps) efficient to do:

        straws = list(set(needle).union(set(haystack)))
        needle_dict = dict(zip(straws), range(len(straws)))



this:

dfa = [[0 for i in range(M)] for j in range(R)]



...does needless iteration.  Instead do:

    dfa = [ list(range(M)) for j in range(R) ]



There's a small bug in:

if len(needle) == 0:
    return 0
if (haystack == None or needle == None or len(haystack) &lt; len(needle) ):
    return -1



... in that you're calling len(needle) before testing if it's None.


It's unclear why you're doing:

global needle_dict



... it may have performance implications (though I'm not positive).