Find the Index of the First Occurrence

Problem statement

A messaging gateway scans a received text for a particular marker before routing it. If the marker occurs more than once, the gateway must use its earliest starting position, since later matches belong to later sections of the message. Your task Find the zero-based index of the first contiguous occurrence of needle in haystack. Return -1 if the marker never occurs. Important details Characters must match exactly and in sequence. Overlapping occurrences are possible. A marker longer than the message cannot match. A match at the beginning has index zero, not one. Worked example In haystack abracadabra, the marker cad begins at index 4: the preceding characters are a, b, r and a. Therefore print 4.

Input format

Two lines: haystack followed by needle.

Output format

Print the first starting index, or -1.

Constraints

1 <= lengths <= 10000; lowercase English letters only.

Sample input

abracadabra
cad

Sample output

4