BF和RK算法

题目：28. 实现 strStr()

BF算法（暴力算法）

 # 暴力做法
    def BF(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i + len(needle)] == needle:
                return i

        return -1

RK算法

# 利用Hash，HashCode相等的可能匹配，HashCode不等的一定不匹配
    def RK(self, haystack: str, needle: str) -> int:

        def get_code(strings: str) -> int:
            ans = 0
            for c in strings:
                ans += ord(c) - ord('a')
            return ans

        needle_code = get_code(needle)
        sub_haystack_code = get_code(haystack[:len(needle)])
        if needle_code == sub_haystack_code and needle == haystack[:len(needle)]:
            return 0

        for i in range(len(needle), len(haystack)):
            sub_haystack_code = sub_haystack_code - (ord(haystack[i - len(needle)]) - ord('a')) + (
                    ord(haystack[i]) - ord('a'))
            if needle_code == sub_haystack_code and haystack[i - len(needle) + 1:i + 1] == needle:
                return i - len(needle) + 1
        return -1

参考

漫画：什么是字符串匹配算法？