給定一個 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() 定義相符。
本題就是要實現一個indexOf函數，首先想到的就是雙指針在兩個串中比較。
暴力解法（BF）就依次掃描如果有相同的同步繼續，出現不同就中斷了，模式串回到起點主串回到下個開頭點。也就是說主串的長度會遍歷完，剩下的看模式串掃到什麼時候中斷。在最差的情況下每次模式串遍歷到最後一個中斷主串最末端才匹配到那就是O(n*m)
邊界
細節
循環結束條件
haystack空返回0
haystack比needle短返回-1
public int strStr(String haystack, String needle) {
char[] hay = haystack.toCharArray();
char[] need = needle.toCharArray();
int h = hay.length;
int n = need.length;
int i=0,j=0;
while(j < h && i < n){
if(hay[j] == need[i]){
i++;
j++;
}else {
j=j-i+1;
i=0;
}
}
if(i >= n) return j-i;
else return -1;
}
除了兩個指針依次比較之外，判斷一個串是否含另一個串直接去依次截取目標長度的子串，判斷有無相等的子串。這裡截取我直接用的substring方法，這個也實現過很多次了，怎麼寫都一樣但我們一定要知道它的實現是怎樣的才能客觀的分析它的複雜度，這裡它就是一次遍歷。
public int strStr(String haystack, String needle) {
int n = needle.length();
int h = haystack.length();
for (int i = 0; i < h - n + 1; i++) {
if (haystack.substring(i, i + n).equals(needle)) {
return i;
}
}
return -1;
}
其實這種解法和解法一是一模一樣只不過前者把截取和比較直接寫了出來，它比解法一優的點只是少遍歷了後面短的部分一個是h * (?)另一個是（h-n+1）* (?)，是因為兩層遍歷分開寫可以這樣做。外面遍歷子串的開頭，裡面再遍歷子串與模式串是否相等。而解法一放到了一個循環也做到了這個邏輯
字符串匹配算法算是一個比較經典的算法，也是在計算機領域實際應用超多的算法。上面無論是解一還是解二其實都是全遍歷比較。許多科學家都發明了更多減少比較次數的方式，比如RK算法、BM算法以及KMP算法。這些在這裡暫時不介紹。之後在其他系列會出單篇講解這類以及其他的算法。