1802. Every Place the Pattern Starts
Given a text t and a pattern p, print every 0-based position in t at which p
begins.
Occurrences may OVERLAP, and all of them are wanted, as positions rather than a count.
mississippi, issi -> 1 4 the two copies share three characters
aaaa, aa -> 0 1 2 three occurrences, not two
abcabc, abc -> 0 3 these touch without overlapping
abc, xyz -> none
Look at mississippi. The copy at 1 covers positions 1 to 4 and the copy at 4
starts inside it. Both count.
## What most people try first
Line the pattern up at every position and compare:
for i in 0 .. n-m:
if t[i .. i+m-1] == p: report i
That is (n - m + 1) * m comparisons in the worst case. At n = 200000 and
m = 1000 it is about 2 * 10^8. At m = 100000 it is about 10^10. The
method below costs about 2 * (n + m), which stays under 10^6 at any of
these sizes.
The other common mistake is cheaper and worse: after a match, jumping forward
by m. On aaaa with aa that prints 0 2 instead of 0 1 2, which was
confirmed by running it.
## Glue them together
Build g = p + '#' + t, where # is a character that appears in neither. Then
compute the prefix function of g from problem 1801.
for i in 2m .. |g|-1:
if pi[i] == m: report i - 2m
## Why the separator matters
pi[i] can never exceed m, because any longer border would have to contain
the #, and # occurs exactly once in g. So pi[i] == m means precisely
that the last m characters ending at i are p. Without the separator a
border could run off the end of p into t and the test would be meaningless.
The occurrence ends at index i of g, so it starts at i - m + 1, and the
text begins at index m + 1, which gives the reported position i - 2m.
Overlapping occurrences come out automatically: the scan never jumps, it simply
reads every character of g once.
## Cost
O(n + m) time and O(n + m) memory. Problem 79 asks for the same search as a
COUNT at a much smaller limit, where the quadratic scan is fine.
Constraints - `1 ≤ length of t ≤ 200000` - `1 ≤ length of p ≤ 200000` - both strings contain only lowercase English letters - `p` may be longer than `t`, in which case there is no occurrence
Input
The first line contains the text t.
The second line contains the pattern p. Both are lowercase English letters.
Output
Print the 0-based starting positions in increasing order on one line, separated by single spaces. Print the single word none if the pattern does not occur.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.