What
- Used for pattern searching
- Complexity
How
Use an auxiliary table, same length as the pattern. The value indicate the offset it will need to move.
Why
Derivation
- We restart from the leftmost prefix of needle in haystack
def strStr(self, haystack: str, needle: str) -> int:
def pi_table(needle):
m = len(needle)
pi = [0] * m
k = 0
for i in range(1, m):
while k > 0 and needle[k] != needle[i]:
k = pi[k - 1]
if needle[i] == needle[k]:
k += 1
pi[i] = k
return pi
pi = pi_table(needle=needle)
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = pi[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - len(needle) + 1
return -1