63. KMP Pattern Search

Given a text and a pattern, find every starting index (0-indexed) in text where pattern occurs (occurrences may overlap). Use the Knuth-Morris-Pratt algorithm (build the pattern's longest-proper-prefix-suffix failure table, then scan text using it to avoid re-comparing already-matched characters). 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

The failure function is built purely from the PATTERN itself (never looking at the text) - this is what makes it reusable across the entire scan, computed just once regardless of how long the text is.

Find every position where a pattern occurs inside a text, using the Knuth-Morris-Pratt algorithm, which cleverly avoids re-checking characters it already knows must match. Brute force: For every starting position in the text, compare the pattern character by character directly, restarting from scratch after every mismatch - this costs O(n*m) in the worst case (imagine a text of all 'a's and a pattern of many 'a's followed by a 'b'). Optimised: The precomputed failure function encodes exactly how much of the pattern's own structure can be REUSED after a partial match fails, letting the pattern pointer jump backward intelligently instead of restarting at 0 - this guarantees the text pointer NEVER needs to move backward, giving a true O(n+m) total time regardless of the input's structure.

Slide the pattern over every possible starting index in text and compare it character by character against the substring beginning there, recording the index whenever all characters match. This checks every alignment directly so it can never miss an occurrence, but a mismatch deep into a comparison throws away all the progress made and restarts from scratch at the next index. Time: O(n*m) Space: O(1)

Compute a rolling hash of the pattern and of every length-|pattern| window of text, sliding the window one character at a time and updating the hash in O(1) using the previous window's hash (subtract the outgoing character's contribution, shift, add the incoming character). Only when a window's hash matches the pattern's hash do we pay for a direct character comparison to rule out a hash collision. This avoids restarting comparisons from nothing on every position the way brute force does, giving expected linear time, though an adversarial input can still force it back down to quadratic time due to collisions. Time: O(n+m) average, O(n*m) worst case Space: O(1)

Precompute the pattern's failure (longest proper prefix that is also a suffix) table in O(m), which for every prefix of the pattern tells you the longest prefix you can fall back to after a mismatch without re-examining already-matched text. Then scan text once, and whenever a mismatch occurs, use the failure table to jump the pattern pointer forward instead of resetting it to zero and re-sliding one position at a time, so no character of text is ever re-compared unnecessarily. This guarantees linear time in the worst case, unlike the hash-based approach, because it never relies on a probabilistic argument. Time: O(n+m) Space: O(m)

1. First, build the pattern's own 'failure function' (also called the LPS array): for every prefix of the pattern, how long is its longest proper prefix that's ALSO a suffix of that same prefix. 2. Scan the text left to right, advancing a pointer into the pattern whenever characters match. 3. On a mismatch, instead of restarting the pattern pointer from 0, jump it back using the failure function's value - this skips re-comparing characters that are guaranteed to match based on the pattern's own internal structure. 4. Whenever the pattern pointer reaches the pattern's full length, record a match (and continue searching for overlapping occurrences using the failure function again).

Time: O(n + m) - building the failure function takes O(m), and the main scan takes O(n), both linear and independent of how many partial matches occur. Space: O(m), for the pattern's failure function array.

Overlapping occurrences of the pattern within the text; pattern equal in length to the text; a pattern that never occurs ('None'); text/pattern up to 10^5 characters for performance.

This is one of the most celebrated string-matching algorithms in computer science - be ready to explain WHY the naive approach can degrade to O(n*m) with a concrete adversarial example, and how KMP's failure function guarantees linear time regardless.