62. Rabin-Karp Pattern Search

Given a text and a pattern, find every starting index (0-indexed) in text where pattern occurs (occurrences may overlap). Use a rolling-hash comparison (Rabin-Karp) to filter candidate positions before confirming a match. Print the indices in ascending order, space-separated; if there are none, print 'None'.

Input: The first line contains the text. The second line contains the pattern. Output: Print the 0-indexed starting positions where pattern occurs in text, ascending and space-separated, or print 'None' if there are none.

1 <= |pattern| <= |text| <= 10^5

Choosing a large prime modulus for the rolling hash calculation is what keeps collisions rare in practice - a poor choice of modulus can degrade Rabin-Karp's real-world performance significantly even though its average-case complexity looks great on paper.

Find every occurrence of a pattern inside a text using a clever 'rolling hash' trick that quickly rules out most non-matching positions before doing an expensive full comparison. Brute force: For every starting position in the text, directly compare the pattern character by character - this costs O(n*m) in the worst case, since a full comparison is attempted at every single position even when most quickly turn out to be non-matches. Optimised: The rolling hash update (computing the next window's hash from the current one in O(1), rather than recomputing from scratch) lets you cheaply screen almost all positions using just a numeric comparison - only positions with a MATCHING hash need the more expensive full character comparison, keeping the expected total work close to O(n+m) in practice.

Slide the pattern across every possible starting index in the text and compare it character by character against the text at that position. If all characters match, record the index. This checks all n - m + 1 positions directly, doing up to O(m) work per position, so it is correct but wasteful because it re-examines overlapping characters from scratch at every shift. Time: O(n*m) Space: O(1)

Compute a hash of the pattern and of every length-m window of the text, but instead of recomputing each window hash from scratch, update it in O(1) using the rolling-hash recurrence (subtract the outgoing character's contribution, shift, add the incoming character). Only when a window's hash matches the pattern's hash do you fall back to a direct character comparison to rule out a hash collision, so genuine mismatches are filtered out in O(1) instead of O(m). Using a large prime modulus (or double hashing with two independent mod/base pairs) keeps collisions negligible in practice, giving expected O(n+m) time overall, which is the technique the problem statement asks for. Time: O(n+m) average Space: O(1)

Build the prefix-function (KMP failure table) or Z-array for the string pattern + separator + text, which lets you track the longest match ending at each position in a single left-to-right pass without ever re-comparing characters you've already matched. Whenever the running match length equals the pattern length, an occurrence ends there. This gives an exact, collision-free O(n+m) guarantee that doesn't depend on hashing at all, unlike the required rolling-hash technique, making it a solid deterministic alternative to compare against. Time: O(n+m) Space: O(n+m)

1. Compute a hash value for the pattern once. 2. Compute a hash value for the FIRST window of text (same length as the pattern). 3. Slide the window one position at a time, updating its hash in O(1) using a 'rolling' update formula (removing the outgoing character's contribution, adding the incoming character's contribution) rather than recomputing from scratch. 4. Whenever a window's hash matches the pattern's hash, do a direct character-by-character comparison to confirm it's a TRUE match (not a rare hash collision) before recording it.

Time: O(n+m) on average (with a good hash function and rare collisions), though O(n*m) in a rare worst case with many hash collisions needing full comparisons. Space: O(1) extra space - just the current rolling hash values, no additional data structures needed.

Overlapping occurrences of the pattern; a pattern equal in length to the text; a rare hash collision that must be confirmed by direct character comparison; text/pattern up to 10^5 characters for performance.

Be ready to explain explicitly why the direct character comparison after a hash match is still necessary (to rule out hash collisions) - skipping this step would risk false positives, a common correctness bug if rushed.