Pattern Search

You are given two strings: a pattern and a text. Your task is to find the starting index (0-indexed) of the first occurrence of the given pattern in the text using an efficient algorithm (for instance, the Knuth-Morris-Pratt algorithm). If the pattern does not exist in the text, output -1.

The solution should handle edge cases, such as when the pattern is longer than the text. Make sure to optimize the pattern search to work efficiently even with large inputs.

inputFormat

The input is read from standard input (stdin) and consists of exactly two lines. The first line contains the pattern string, and the second line contains the text string in which you are to search for the pattern.

outputFormat

The output is a single integer printed to standard output (stdout) which represents the starting index (0-indexed) of the first occurrence of the pattern in the text. If the pattern is not found, output -1.

abc
ababcabc

2