'''

def strStr(self, haystack, needle):

```
if not needle: return 0
j = 0; i = 1;
lps = [None] * len(needle)
lps[0] = 0
while i< len(needle):
if needle[i] == needle[j]:
lps[i] = j+1
i += 1
j += 1
else: # needle[i] != needle[j]
if j != 0:
j = lps[j-1]
else: # j == 0
lps[i] = 0
i += 1
nIdx = 0; hIdx = 0
while hIdx < len(haystack):
if needle[nIdx] == haystack[hIdx]:
nIdx += 1
hIdx += 1
if nIdx == len(needle):
return hIdx - nIdx
else:
if nIdx != 0:
nIdx = lps[nIdx -1]
else:
hIdx += 1
return -1
```

'''