# Rolling Hash Search

# Rolling Hash Search

Rolling hash search computes a hash over a fixed size window and updates it efficiently as the window moves. It allows substring search in linear time with low constant factors.

You use it when scanning large text for patterns or when building string matching algorithms such as Rabin Karp.

## Problem

Given a text $T$ of length $n$ and a pattern $P$ of length $m$, find all indices $i$ such that:

$$
T[i \dots i + m - 1] = P
$$

## Model

Define a polynomial hash for a string:

$$
H(s_0 s_1 \dots s_{m-1}) = (s_0 \cdot B^{m-1} + s_1 \cdot B^{m-2} + \dots + s_{m-1}) \bmod M
$$

For a sliding window, the hash updates as:

$$
H_{i+1} = \big((H_i - s_i \cdot B^{m-1}) \cdot B + s_{i+m}\big) \bmod M
$$

This avoids recomputing the hash from scratch.

## Algorithm

```text id="6r5zpn"
rolling_hash_search(T, P):
    n = length(T)
    m = length(P)

    target = hash(P)
    current = hash(T[0..m-1])

    for i from 0 to n - m:
        if current == target:
            if T[i..i+m-1] == P:
                report match at i

        if i < n - m:
            current = update_hash(current, T[i], T[i+m])

    return all matches
```

## Example

Let:

$$
T = "abracadabra"
$$

$$
P = "abra"
$$

Sliding windows:

| index | substring | hash match |
| ----: | --------- | ---------- |
|     0 | abra      | yes        |
|     1 | brac      | no         |
|     2 | raca      | no         |
|     3 | acad      | no         |
|     4 | cada      | no         |
|     5 | adab      | no         |
|     6 | dabr      | no         |
|     7 | abra      | yes        |

Matches at indices 0 and 7.

## Correctness

The rolling hash ensures that every substring of length $m$ is assigned a hash value. When the hash matches the pattern hash, a direct comparison verifies the match.

The direct comparison eliminates false positives caused by hash collisions.

## Complexity

| operation     | time               |
| ------------- | ------------------ |
| preprocessing | $O(m)$             |
| search        | $O(n)$             |
| verification  | depends on matches |

Total time is $O(n + m)$ in expectation.

## Space

$$
O(1)
$$

Only a few integer values are stored.

## When to Use

Rolling hash search is appropriate when:

* substring matching is required
* repeated hash computation must be avoided
* large texts are processed
* approximate matching is combined with verification
* multiple pattern checks are needed

It is widely used in string matching, plagiarism detection, deduplication, and substring indexing.

## Implementation

```python id="1n9qks"
def rolling_hash_search(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    B = 256
    M = 10**9 + 7

    def hash_str(s):
        h = 0
        for c in s:
            h = (h * B + ord(c)) % M
        return h

    target = hash_str(pattern)
    current = hash_str(text[:m])

    power = pow(B, m - 1, M)
    result = []

    for i in range(n - m + 1):
        if current == target:
            if text[i:i+m] == pattern:
                result.append(i)

        if i < n - m:
            current = (current - ord(text[i]) * power) % M
            current = (current * B + ord(text[i + m])) % M

    return result
```

```go id="8j0mwx"
func RollingHashSearch(text, pattern string) []int {
	n, m := len(text), len(pattern)
	if m > n {
		return nil
	}

	const B = 256
	const M = 1000000007

	hashStr := func(s string) int {
		h := 0
		for i := 0; i < len(s); i++ {
			h = (h*B + int(s[i])) % M
		}
		return h
	}

	target := hashStr(pattern)
	current := hashStr(text[:m])

	power := 1
	for i := 0; i < m-1; i++ {
		power = (power * B) % M
	}

	var result []int

	for i := 0; i <= n-m; i++ {
		if current == target && text[i:i+m] == pattern {
			result = append(result, i)
		}

		if i < n-m {
			current = (current - int(text[i])*power%M + M) % M
			current = (current*B + int(text[i+m])) % M
		}
	}

	return result
}
```