Problem

Given a text string T of length n and a pattern string P of length m, return all starting indices (0-based) where P occurs in T. Implement the Rabin–Karp rolling-hash algorithm rather than a naive character-by-character compare.

Input / Output

• Input: strings T and P over lowercase letters (or any fixed alphabet).
• Output: list of starting indices, in increasing order; empty list if none.

Examples

Example 1 Input: T = "abracadabra", P = "abra" Output: [0, 7]

Example 2 Input: T = "aaaaa", P = "aa" Output: [0, 1, 2, 3]

Constraints

• 1 <= m <= n <= 10^6

Approach

The naive algorithm checks every window in O(m), giving O(n·m). Rabin–Karp reduces this by comparing hash values of windows first and only comparing characters when hashes match.

Polynomial rolling hash. Treat a string as a number in base B (a prime larger than the alphabet size, e.g. 31 or 257) modulo a large prime M (e.g. 10^9+7): hash(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + … + s[m-1]) mod M

Sliding the window. When moving from window starting at i to i+1: newHash = ((oldHash − T[i]·B^(m-1)) · B + T[i+m]) mod M Precompute B^(m-1) mod M once. Keep everything non-negative by adding M before taking the modulus.

Algorithm.

1. Compute hashP and the hash of the first window of T.
2. For each window: if the hash equals hashP, compare the characters directly to confirm (this guards against collisions). Record the index if they match.
3. Roll the hash to the next window.

Collisions. Two different strings can share a hash. The direct comparison on hash match keeps the algorithm correct; using a double hash (two moduli) makes false matches astronomically rare so the verification almost never runs.

Complexity

• Time: O(n + m) on average; O(n·m) in the pathological worst case where every window collides.
• Space: O(1) beyond the output.

When to prefer it

Rabin–Karp shines for multiple-pattern search (hash all patterns of the same length into a set and scan once) and for problems like "longest duplicate substring", where KMP does not apply directly.

Reference solution (Python)

def rabin_karp(text, pat, B=257, M=10**9 + 7):
    n, m = len(text), len(pat)
    if m > n:
        return []
    high = pow(B, m - 1, M)
    hp = ht = 0
    for i in range(m):
        hp = (hp * B + ord(pat[i])) % M
        ht = (ht * B + ord(text[i])) % M
    res = []
    for i in range(n - m + 1):
        if hp == ht and text[i:i + m] == pat:
            res.append(i)
        if i + m < n:
            ht = ((ht - ord(text[i]) * high) * B + ord(text[i + m])) % M
    return res

Test cases

Input	Expected
text="abracadabra", pat="abra"	[0, 7]
text="aaaaa", pat="aa"	[0, 1, 2, 3]
text="abc", pat="d"	[]
text="ab", pat="abc"	[]