Stamp a String into the Target
Starting from a blank string of '?' characters, you repeatedly stamp a fixed pattern over a window, overwriting those positions. Recover a sequence of stamp positions that produces the target.
Problem
Given strings stamp and target of equal alphabet, beginning with target.length copies of '?', you may overlay stamp at any position so its characters overwrite that window. Return any sequence of stamp start positions (length at most 10 * target.length) whose application turns the blank string into target; return an empty array if impossible.
Input
Two strings stamp and target.
Output
An array of stamp start indices (the order they should be applied), or an empty array.
Constraints
- 1 <= stamp.length <= target.length <= 1000
- stamp and target consist of lowercase letters.
Examples
Example 1
Input
stamp = "abc", target = "ababc"
Output
[0,2]
Stamp at 2 then 0 (the returned order is the forward application 0 then 2).
Example 2
Input
stamp = "abca", target = "aabcaca"
Output
[3,0,1]
A valid stamping order that builds the target.