1
\$\begingroup\$

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?

\$\endgroup\$
7
  • 3
    \$\begingroup\$ How large does n get? Thinking about the implications of this: 10**(n-i-1). \$\endgroup\$
    – FMc
    Dec 2 '21 at 3:16
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – Peilonrayz
    Dec 2 '21 at 3:17
  • 2
    \$\begingroup\$ Micro review: range(1, 29) should be range(1, 27). \$\endgroup\$
    – Marc
    Dec 2 '21 at 4:49
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – RootTwo
    Dec 2 '21 at 6:41
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Dec 2 '21 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.