Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
def find_anagrams(hay, needle):
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
f = lambda c : primes[ord(c.lower()) - ord('a')]
needle_primes = map(f, needle)
needle_primehash = reduce(mul, needle_primes)
current_primehash = 1
l = len(needle)
locations = []
for i,c in enumerate(hay):
if i >= l:
current_primehash //= f(hay[i - l])
current_primehash *= f(c)
if needle_primehash == current_primehash:
locations.append((i - l + 1, hay[i-l+1:i+1]))
return locations
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment