140-28. 实现 strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。(两个都是我写的,暴力破解搞得还可以写,但是kmp算法,我只能去网上找的改编成python代码)
估计没有十年脑血栓我是写不出来kmp算法了(我用手可以推出来next_数组,但是代码部分就是不知道如何实现难受)
class Solution(object):
    def strStr1(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        i = 0
        j = 0
        length = len(haystack)
        length2 = len(needle)
        while i < length and j < length2:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                i = i - j + 1
                j = 0

        if j == length2:
            return i - length2
        else:
            return -1

    def strStr(self, haystack, needle):
        """KMP算法
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0

        if not haystack:
            return -1

        next_ = self.kmp(needle)
        i = 0
        j = 0
        while i < len(haystack):
            while j > 0 and haystack[i] != needle[j]:
                j = next_[j-1]
            if haystack[i] == needle[j]:
                j += 1
            if j == len(needle):
                return i - j + 1
            i += 1
        return -1

    def kmp(self, dest):
        """kmp算法next_数组创建"""
        next_ = [0] * len(dest)
        i = 1
        j = 0
        while i < len(dest):
            while j > 0 and dest[i] != dest[j]:
                j = next_[j-1]

            if dest[i] == dest[j]:
                j += 1
            next_[i] = j
            i += 1
        return next_


if __name__ == '__main__':
    haystack = "hello"
    needle = "ll"
    s1 = Solution()
    print(s1.kmp(needle))
    print(s1.strStr(haystack, needle))