# LeetCode 028Implement strStr()

## LeetCode 028 Implement strStr() Problem

``````class Solution(object):
# def strStr(self, haystack, needle):
#     """
#     :type haystack: str
#     :type needle: str
#     :rtype: int
#     """
#     lsh, lsn = len(haystack), len(needle)
#     if lsn == 0:
#         return 0
#     pos, index = 0, 0
#     while index <= lsh - lsn:
#         if haystack[index] == needle[pos]:
#             backup = index
#             while index < lsh and pos < lsn and haystack[index] == needle[pos]:
#                 pos += 1
#                 index += 1
#             if pos == len(needle):
#                 return index - pos
#             index = backup
#         index += 1
#         pos = 0
#     return -1

# def strStr(self, haystack, needle):
#     lsh, lsn = len(haystack), len(needle)
#     if lsn == 0:
#         return 0
#     pos, index = 0, 0
#     while index <= lsh - lsn:
#         if haystack[index] == needle:
#             # slice index:index + lsn
#             if haystack[index:index + lsn] == needle:
#                 return index
#         index += 1
#     return -1

# KMP
# https://discuss.leetcode.com/topic/3576/accepted-kmp-solution-in-java-for-reference/2
def strStr(self, haystack, needle):
lsh, lsn = len(haystack), len(needle)
if lsn == 0:
return 0
next = self.makeNext(needle)
i = j = 0
while i < lsh:
if j == -1 or haystack[i] == needle[j]:
i += 1
j += 1
if j == lsn:
return i - lsn
if i < lsh and haystack[i] != needle[j]:
j = next[j]
return -1

def makeNext(self, needle):
ls = len(needle)
next =  * ls
next, i, j = -1, 0, -1
while i < ls - 1:
if j == -1 or needle[i] == needle[j]:
next[i + 1] = j + 1
if needle[i + 1] == needle[j + 1]:
next[i + 1] = next[j + 1]
i += 1
j += 1
if needle[i] != needle[j]:
j = next[j]
return next

``````