28.md

题目地址

https://leetcode-cn.com/problems/implement-strstr/

解答

def strStr(haystack, needle):
    """
        实现strStr

        查找子串位置，sunday算法实现
    """
    hashmap = {}
    for i, c in enumerate(needle):
        hashmap[c] = i

    nn = len(needle)
    nh = len(haystack)
    i = 0
    while i <= nh - nn:
        j = nn - 1
        while j >= 0:
            if haystack[i + j] != needle[j]:
                if i + nn < nh:
                    skip = nn - hashmap.get(haystack[i + nn], -1)
                else:
                    return -1
                break
            j -= 1
        if j == -1:
            return i
        i += skip
    return -1