28. 实现 strStr()

Difficulty
easy
Tags
字符串
URL
https://leetcode-cn.com/problems/implement-strstr/
Star
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
示例 3：
输入：haystack = "", needle = ""
输出：0
提示：
  • 0 <= haystack.length, needle.length <= 5 * 104
  • haystack 和 needle 仅由小写英文字符组成

法1 字符串hash

思路
采用滑动窗口向后计算字符串的hash，然后逐个匹配。
 
题解
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 先进行边界判断
        if len(needle) == 0:
            return 0
        elif len(haystack) == 0:
            return -1
        
        # 再进行字符串匹配
        MOD = 10 ** 6
        BASE = 31

        # 计算目标串的 hash
        target_hash = 0
        power = 1
        for i in range(len(needle)):
            target_hash = (target_hash * BASE + ord(needle[i])) % MOD
            power = (power * BASE) % MOD

        # 滑动窗口计算源字符子串的hash
        source_hash= 0
        for i in range(0, len(haystack)):
            
            # 当前字串 为 haystack[i-len(needle)+1:i+1]
            source_hash = ((source_hash * BASE) % MOD + ord(haystack[i])) % MOD
            
            # 长度不够目标子串的情况下，不判断只向后计算
            if i < len(needle)-1:
                continue

            if i >= len(needle):
                # 将当前子串最 前一位字符hash移除掉
                source_hash = (source_hash - ord(haystack[i-len(needle)]) * power) % MOD

            # 判断当前子串的hash 是否和目标串hash 相同，
            # 如果相同，再进一步判断子串
            if source_hash == target_hash:
                if haystack[i-len(needle)+1: i+1] == needle:
                    return i - len(needle) + 1

        return -1
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) > len(haystack):
            return -1
        MOD = 2 ** 64
        BASE = 131

        # 对 needle 进行 hash
        power = 1
        target = 0
        for i in range(0, len(needle)):
            target = (target * BASE + (ord(needle[i]) - ord("a") + 1) ) % MOD
            if i < len(needle)-1:
                power = power * BASE % MOD
    
        # 遍历 搜索
        source = 0
        i = 0
        while i < len(haystack):
            while i < len(needle) - 1:
                source = (source * BASE + (ord(haystack[i]) - ord("a") + 1)) % MOD
                i += 1
            
            source = (source * BASE + (ord(haystack[i]) - ord("a") + 1)) % MOD
            # print(i, source)
            if source == target:
                return i - len(needle) + 1
            
            source = (source - (ord(haystack[i-len(needle)+1]) - ord("a") + 1) * power + MOD) % MOD

            i += 1

        return -1