Rabin-Karp Search

Problem

Return the sorted starting indices of all occurrences of pattern in text using the Rabin-Karp rolling hash.

Hash the pattern and the first window with base 256 modulo 101, roll the window in O(1), and verify any hash match character by character. Return an empty list when the pattern is empty or longer than the text.

Hint

Hash equality is only a candidate; always verify the characters to rule out collisions.

Test cases

case 1

in: ["ababcababa","aba"]

expected: [0,5,7]

case 2

in: ["aaaa","aa"]

expected: [0,1,2]

case 3

in: ["abc","d"]

expected: []

case 4

in: ["a","a"]

expected: [0]

case 5

in: ["","a"]

expected: []

Starter codePython

def rabin_karp_search(text, pattern):
    # Your code here
    pass

5 test cases · run your code against them in the editor