28.實(shí)現(xiàn)strStr（）

實(shí)現(xiàn) strStr() 函數(shù)。

給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)。如果不存在，則返回 -1。

示例 1:

輸入: haystack = "hello", needle = "ll"
輸出: 2
示例 2:

輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
說明:

當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問題。

對(duì)于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/implement-strstr
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路：

用Sunday算法來求解。

什么是Sunday算法呢？
目標(biāo)字符串：S
模式串：P
當(dāng)前查詢索引：i
待匹配字符串：now_str 為 S[ i ： i+len(P) ]

每一次都從目標(biāo)字符串中提取待匹配的字符串與模式串進(jìn)行匹配：
如果匹配的話，就返回當(dāng)前的 i
不匹配的話，查看待匹配字符串的后一位字符c，判斷這個(gè)字符c在不在模式串P中：
如果在的話，則 i = i + 偏移表 [ c ]
不在的話，則 i = i + len(P)
直到 i + len(P) > len(S) 循環(huán)結(jié)束。

偏移表

偏移表的作用是存儲(chǔ)每一個(gè)模式串中出現(xiàn)的字符，在模式串中出現(xiàn)的最右位置到尾部的距離 + 1，如 bba：
b 的偏移位 ：len(P) -1 = 2
a 的偏移位： len(P) -2 = 1
其他的偏移位為 ： len(P）+ 1 = 4

舉例
S: hello
P: ll

第一步：
i = 0
待匹配字符串為：he
發(fā)現(xiàn) he != ll
查看he后一位字符 l
l 在 P 中
查詢偏移表，l 的偏移位： len(P) = 2 - 1 = 1
i = 0 + 1 = 1

第二步：
idx = 1
待匹配字符串：el
因?yàn)?el ！= ll
查看 el 后一位字符 l
l 在 P 中
查詢偏移表，l 的偏移位： len(P) = 2 - 1 = 1
i = 1 + 1 = 2

第三步：
idx = 2
待匹配字符串：ll
因?yàn)?ll == ll
匹配，返回 2

時(shí)間復(fù)雜度

平均情況：O（n）
最壞情況：O（nm）

程序代碼：

def find_p(haystack,needle):
    #計(jì)算偏移表
    def shift_s(s):
        dic = {}
        for i in range(len(s)-1,-1,-1):
            if not dic.get(s[i]):
                dic[s[i]] = len(s) - i
        dic['other'] = len(s) + 1
        # print(dic)
        return dic
 
 
    dic = shift_s(needle)
    h_len = len(haystack)
    n_len = len(needle)
    i = 0
    while i + n_len <= h_len:
        now_str = haystack[i:i+n_len]
        if now_str == needle:
            return i
        else:
            if i + len(needle) >= len(haystack):
                return -1
            next_s = haystack[i+n_len]
            if dic.get(next_s):
                i += dic[next_s]
            else:
                i += dic['other']
 
    return -1 if i + len(needle) >= len(haystack) else i
 
 
haystack = "hello"
needle = "ll"
print(find_p(haystack, needle))