1816. Searching by Gluing the Pattern to the Front
Given a text t of length n and a pattern p, print a line of exactly n
characters: a 1 at every position where an occurrence of p STARTS and a 0
everywhere else.
Occurrences may OVERLAP, and the answer is a mask over positions rather than a count.
aaaa, aa -> 1110
mississippi, issi -> 01001000000
abcabc, abc -> 100100
abc, xyz -> 000
abc, abcd -> 000
The mask always has exactly n characters, even when nothing matches and even
when the pattern is longer than the text. The last |p| - 1 positions are
always 0, because a match starting there would run off the end.
## What most people try first
Compare the pattern at every position: (n - m + 1) * m comparisons, about
2 * 10^8 at n = 200000 and m = 1000. The Z array below does about
4 * 10^5.
The instructive wrong version marks a match and then skips m positions ahead.
On aaaa with aa it prints 1010 instead of 1110, which was confirmed by
running it.
## The pattern goes in front
g = p + '#' + t
z = Z array of g
position i of t is a match <=> z[m + 1 + i] >= m
## Why the separator caps it and why that is what you want
z[j] counts how far position j of g agrees with the BEGINNING of g,
which is p. Because # occurs exactly once and appears in neither p nor
t, no agreement can reach past position m, so z[j] is at most m for
every j after the separator.
Therefore z[j] >= m means z[j] is exactly m, which says the m characters
of g starting at j are p. Translating j = m + 1 + i back to the text
gives position i.
Nothing is ever skipped, so overlapping matches all appear.
## The prefix function does this too
Problem 1802 solves the same search with the prefix function and reports
positions. Both glue with a separator; the difference is what the table means.
The prefix function asks what ends at a position and detects a match when the
value REACHES m. The Z array asks what starts at a position and detects a
match at the position itself, which is why this version needs no arithmetic to
convert an end back into a start beyond the fixed offset.
## Cost
O(n + m) time and memory.
Constraints - `1 ≤ length of t ≤ 200000` - `1 ≤ length of p ≤ 200000` - both strings contain only lowercase English letters - occurrences may overlap, and `p` may be longer than `t`
Input
The first line contains the text t.
The second line contains the pattern p. Both are lowercase English letters.
Output
Print one line of exactly n characters, where n is the length of the text: 1 at each position where an occurrence of the pattern begins and 0 at every other position. Print the line even when it is all zeros.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.