String search using Rabin-Karp algorithm

I am trying to solve a needle in haystack using Rabin-Karp algorithm, but for large inputs my code takes way too long time. Here is the part which apparently is too slow:

char_map = dict(zip(list("abcdefghijklmnopqrstuvwxyz"), list(range(1, 29))))

def hash_function(s):
hash = 0
n = len(s)
for i, ch in enumerate(s):
hash += char_map[ch] * 10**(n-i-1)
return hash


Since the runtime complexity of this function is $$\O(n)\$$, I do not understand why it is being so slow (I only call this function twice in my solution).

For comparison, I solved the problem using a very naive method, which also has a runtime complexity of $$\O(n)\$$.

def strStr(self, haystack: str, needle: str) -> int:

if len(needle) > len(haystack):
return -1

if not needle:
return 0

for i, ch in enumerate(haystack):
if ch == needle[0]:
if i+len(needle) <= len(haystack) and needle == haystack[i:i+len(needle)]:
return i
return -1


But this one managed to go through the same large input without any issues. What am I doing incorrectly?

• How large does n get? Thinking about the implications of this: 10**(n-i-1).
– FMc
Dec 2 '21 at 3:16
• hash will be at most $10^{5 \times 10^4} = 2^{166096} = 2^{2595 * 64 + 16}$. So you'll be adding 2.6k ints (assuming the underlying ints are 64bit) together 50k times. I don't think Python's ints are designed for that. Dec 2 '21 at 3:17
• Micro review: range(1, 29) should be range(1, 27).
– Marc
Dec 2 '21 at 4:49
• To be efficient, the hash function used in the Rabin-Karp algorithm needs to be a rolling hash. Otherwise, the algorithm takes O(n * m), where n and m are the lengths of the needle and the haystack. Your hash doesn't appear to be a rolling hash. Dec 2 '21 at 6:41
• Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Please check that I haven't misrepresented your code, and correct it if I have. Dec 2 '21 at 8:18