Hashing

Pattern Matching Hashing

Rolling hashing turns substrings into comparable numeric fingerprints and updates them in constant time while sliding.

Kind

rolling

Time

O(N + M)

Space

O(N)

Steps

Input Keys

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Hash Table / State

bucket 0

empty

bucket 1

empty

bucket 2

empty

bucket 3

empty

bucket 4

empty

bucket 5

empty

bucket 6

empty

bucket 7

empty

bucket 8

empty

bucket 9

empty

Step Timeline

Code + Variables

1hash = hash * base + char

2slide window by removing old char

3compare pattern hash

4verify matching window

patternabra

Loading Lab...