#231EasyString Matching· Knuth-Morris-Pratt Search

Find Error Code in Log

An operations team keeps every service message in one long text line, the `log`. When a pager alert fires, an engineer wants to know where a given error `code` first shows up in that line so the surrounding messages can be inspected. Return the zero-based index of the **first** place where `code` occurs inside `log` as a contiguous block of characters, or `-1` if it never occurs. An empty `code` occurs at index `0`. Scanning from every start position and comparing character by character can degrade to `O(n * m)` when the log is full of near matches such as `aaaa...ab`. A linear solution reuses what a failed comparison already told it.

Input format

`log`: a string. `code`: a string.

Output format

An integer: the first index at which `code` starts in `log`, or -1.

Examples

Input: log = "INFO boot ok ERR-42 retry ERR-42 done", code = "ERR-42"

Output: 13

The code ERR-42 appears twice. Its first occurrence starts at index 13, right after "INFO boot ok ".

Input: log = "disk full", code = "net"

Output: -1

The three letters n, e, t never appear as a block in the log, so the answer is -1.

Input: log = "aaaaaab", code = "aaab"

Output: 3

A naive scan fails at several start positions because of the long run of a. The block aaab starts at index 3.

Constraints

0 <= log.length <= 10^5
0 <= code.length <= 10^4
`log` and `code` contain printable ASCII letters, digits, spaces and `-` only.

#strings
#string-matching
#kmp
#prefix-function