實(shí)現(xiàn) strStr()

題目描述：實(shí)現(xiàn) strStr() 函數(shù)。

給你兩個(gè)字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。如果不存在，則返回 ?-1 。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/implement-strstr/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：窮舉法

• 首先，如果needle為空，直接返回0；如果 haystack 為空 或者 haystack 的長度 小于 needle 的長度，直接返回-1；

• 否則，從 haystack 的第一位開始跟 needle 進(jìn)行匹配，如果匹配不上，則往后繼續(xù)遍歷haystack，直到遍歷完成，就能得到結(jié)果。

說明：該方法效率比較差。

解法二：KMP算法

首先，構(gòu)造一個(gè)next數(shù)組，先計(jì)算出下一次跳轉(zhuǎn)的位置，然后遍歷按照next數(shù)組的位置將原串和匹配串進(jìn)行匹配。

【每日寄語】 在最美的年華，做最喜歡的事情，別辜負(fù)了美好時(shí)光，借時(shí)光之手，暖一處花開，借一方晴空，擁抱夢想。