LeetCode-28.實現 strStr()(Implement strStr())

28. 實現 strStr()

實現C語言中的strStr()函數。

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串首次出現位置 (從0開始)。如果不存在，則返回 -1。

示例 1:

輸入: haystack = "hello", needle = "ll"輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba"輸出: -1
說明:
當 needle 是空字符串時，我們應當返回什麼值呢？這是一個在面試中很好的問題。
對於本題而言，當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/implement-strstr/
Link：https://leetcode.com/problems/implement-strstr/
暴力破解
O(M*N)
逐個比較，如果不匹配，右移動一格
ABCDEFG    ->    ABCDEFG    ->    ABCDEFG    ->    ABCDEFG     DEF               DEF               DEF               DEF
代碼如下:
class Solution:    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) > len(haystack):            return -1
        index = 0        for i in range(len(haystack) - len(needle) + 1):            index = i            for j in range(len(needle)):                if needle[j] != haystack[i + j]:                    index = -1                    break
            if index == i:                break
        return index
Robin-karp算法
O(M + N), 如果哈希函數衝突很小的情況下, 不然就退化成暴力破解了
Robin-karp是對暴力破解的一個優化，將Pattern字符哈希取值。每次匹配只比較同長度字符串的哈希值。
如果哈希值相等，考慮到哈希衝突，需再次比較每一位字符。用來驗證結果。
ABCDEFGABC    --哈希值-->   Hash(ABC) BCD    --哈希值-->   Hash(BCD)  CDE    --哈希值-->   Hash(CDE)   ...     DEF    --哈希值-->   Hash(DEF)
比較同長哈希值, 如果相等，逐個比較驗證結果
hash(ABC)        hash(BCD)        hash(CDE)        hash(DEF)    !=               !=               !=               == (需驗證結果)hash(DEF)        hash(DEF)        hash(DEF)        hash(DEF)
ABCDEFG    ->    ABCDEFG    ->    ABCDEFG    ->    ABCDEFGDEF               DEF               DEF               DEF
考慮到Hash的時間複雜度也是O(N), 那麼這個過程，並沒有優化時間複雜度，仍然是(M - N + 1）次比較, 每次哈希O(N)。
如果設計哈希函數如下, 就不必重複計算，每次去掉最高位，乘以K進位，再加上新的最低位
f(ABC) = A * K^2 + B * K^1 + C * K^0f(BCD) =           B * K^2 + C * K^1 + D * K^0
存在遞推關係:f(BCD) = (f(ABC) - A * k^2) * k + D
令k=256進位, 代碼如下:
k_buckets = 131k_characters = 256class Solution:    def strStr(self, haystack: str, needle: str) -> int:
        m = len(haystack)        n = len(needle)
        if n == 0:            return 0
        if n > m:            return -1
        target = 0        tmp = 0        high = 1
        for i in range(n - 1):             high = (high * k_characters) % k_buckets
        for i in range(n):             tmp = (tmp * k_characters + ord(haystack[i])) % k_buckets            target = (target * k_characters + ord(needle[i])) % k_buckets
        for i in range(m - n + 1):            index = i            if tmp == target:                for j in range(n):                    if haystack[i + j] != needle[j]:                        index = -1                        break
                if index == i:                    return index
            if i < m - n:                                                tmp = ((tmp - ord(haystack[i]) * high) * k_characters  + ord(haystack[i + n])) % k_buckets
        return -1
--End--