17 lines (12 loc) · 323 Bytes

Problem 2: Rabin-Karp Algorithm

Problem Statement

Implement Rabin-Karp rolling hash for pattern matching.

Input Format

A text t and pattern p.

Output Format

List of starting indices.

Constraints

1 <= len(p) <= len(t) <= 10^5

Example

Input: t="abcabcabc", p="abc"
Output: [0, 3, 6]