StringKMPPattern Matching
Given a text and a pattern, find the index of the first place the pattern occurs inside the text. Many languages have this built in, but interviewers want to see if you can do it without rescanning characters.
Input
Line 1: the text. Line 2: the pattern. Both are lowercase letters.
Output
Print the 0-based index of the first occurrence, or -1 if the pattern does not occur.
Constraints
1 <= length of text, pattern <= 10^5
Example 1
Input
sadbutsad sad
Output
0
sad first occurs at index 0.
Example 2
Input
leetcode leeto
Output
-1
The pattern never appears.