Rabin–Karp Pattern Search

Given text *T* and pattern *P* (both lowercase), find all starting indices where *P* occurs in *T*. (Use rolling hash).

Input Format

Two lines: text T, then pattern P.

Output Format

Space-separated starting indices (0-based).

Constraints

  • 0 <= len(P) <= len(T) <= 10^5. Lowercase letters.

Examples

Example 1:

Input:

text = "geeksforgeeks"
pattern = "geeks"

Output:

0 8

Explanation:

Pattern "geeks" starts at indices 0 and 8.

Loading...
Rabin–Karp Pattern Search - Strings DSA Problem