284. Stamping The Sequence (Stamp Count)

You want to form target by stamping the string stamp over an initially all-'?' sequence of the same length; each stamp overwrites a window. Return the minimum number of stamps needed (a valid greedy count), or -1 if target cannot be formed. Input: '"stamp", "target"'.

Input: '"stamp", "target"'.

Output: Integer — number of stamps, or -1.

Examples

Input: "abc", "ababc"
Output: 2
Explanation: Stamp at positions 2 then 0.

Input: "abca", "aabcaca"
Output: 3
Explanation: Three stamps.

Input: "abc", "abc"
Output: 1
Explanation: Single stamp.

Constraints

• 1<=stamp.length<=stamp<=target.length<=1000

Asked by