strStr

作為刷提筆記第一道題，其實還是有很多東西值得參考的，相對于其他的題目，字符串操作類的題目很容易把邊界條件的加減搞錯。要注意以下幾點：

1. 當(dāng)要以兩個字符串長度相減作為結(jié)束點是一定要"source.length() - ?target.length() +1"因為減的結(jié)果是最后一個字符所在的位置，而不是最后一個字符后面一位。

2.當(dāng)輸入等于null時一定要問清面試官到底要返回值是什么。

這是第一種算法，第二種是取模算法，第三種是KMP

取模算法的核心思想是sliding window，主要分為以下三個步驟：

1.loop over 通過公式算出target的密碼模。

2.loop over整個string然后每個字符不斷取模，當(dāng)?shù)竭_target相同個數(shù)字符之后比較與target模是否相同，如果相同的話就再比較字符串字符。當(dāng)string里比較字符的個數(shù)超過target的個數(shù)就扔掉前面的字符的模然后繼續(xù)比較。

這樣做的時間復(fù)雜度近似于m+n，因為當(dāng)兩個字符串模相同的情況一般情況下就是兩個字符串相等的情況（哈希碰撞）

程序：

KMP核心思想就是先找出target字符串中重復(fù)的部分，然后loop over字符串，當(dāng)比較前面位相同時，從重復(fù)的最后一段開始繼續(xù)往后面比較，這樣的時間復(fù)雜度是M+N

但是總感覺上面的這種方法2更簡單易于理解