Modified KMP Algorithm

Search a pattern in a string and give the first index of occurrence, but the pattern can contain a wildcard character *, which can match any single character in the string.

You are given two strings, text and pattern. The pattern matches text at index i when every character of pattern lines up with text[i + j]:

1. A letter must equal the character at the same position.
2. A * matches exactly one character, whatever it is. It never matches an empty string or several characters.

Return the smallest index i where pattern matches, or -1 if it matches nowhere. text never contains *.

Example 1

Input:  text = "xacbabca", pattern = "a*c"
Output: 4

At index 1, "acb" fails because b is not c. At index 4, "abc" matches: a, then any character, then c.

Example 2

Input:  text = "ababb", pattern = "a*b"
Output: 2

Index 0 ("aba") and index 1 ("bab") fail; index 2 ("abb") matches. Plain KMP that treats * as equal to everything reports index 1 here, which is wrong.

Example 3

Input:  text = "aaaa", pattern = "a*b"
Output: -1

No b ever appears two places after an a.

Constraints

• 1 <= text.length, pattern.length <= 10^5
• text has lowercase English letters only; pattern has lowercase English letters and *.
• pattern contains at most 10 wildcards.
• If pattern is longer than text, the answer is -1.