KMP Substring Search

Implement substring search. Given a text and a pattern, return the index of the first occurrence of pattern in text, or -1 if it does not exist.

If pattern is empty, return 0.

Function signature

func KMPSearch(text, pattern string) int

Example

text = "hello"
pattern = "ll"
output = 2

Constraints

• 0 <= len(text), len(pattern) <= 200_000

Notes

• Use the Knuth–Morris–Pratt (KMP) algorithm with a prefix table.