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
說(shuō)明:
當(dāng) needle 是空字符串時(shí)譬巫，我們應(yīng)當(dāng)返回什么值呢组哩？這是一個(gè)在面試中很好的問題等龙。
對(duì)于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 伶贰。這與C語(yǔ)言的 strstr() 以及 Java的 indexOf() 定義相符蛛砰。
來(lái)源：力扣（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算法來(lái)求解。
什么是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))
