## String Finding

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

You have a string (indexed from ) with no more than lowercase characters. Find the first occurrence of a string , or print -1 if is not a substring of .

#### Input Specification

The first line will have the string .
The second line will have the string .

#### Output Specification

Print the index of the first occurrence of the string in , or -1 if it is not a substring of .

#### Sample Input

higuyshowsitgoinghiguys
higuys

#### Sample Output

0

Python's builtin find uses Boyer-Moore, which has a worst-case runtime of . Rabin-Karp and KMP are two algorithms which have a worst-case runtime of .