strstr()函數是一個比對函數，判斷一個字元串是否包含另外一個字元串，并傳回被包含字元串的起始位置。如果使用暴力比對的話，時間複雜度非常高，最佳解法是使用KMP算法，但是LeetCode把這道題目定義為簡單題也是挺離譜的。
題目連結：https://leetcode.cn/problems/implement-strstr/
1、KMP介紹和原理
KMP字首表怎麼計算，為什麼要使用字首表，字首表怎麼使用代碼實作，可以看一下這個連結。KMP介紹。
2、KMP了解
在已了解字首表的基礎上，加上一點自己的了解。雖然知道字首表每一位就是對應位置上的子串的最長相等前字尾長度，但是這個長度是怎麼比對的，同時和暴力比對之間，為什麼時間複雜度會由O(MxN)變為O(M+N)呢。
我這裡就舉例一下，str = aabaabaafa，下方的數字表示索引，上方的數字表示字首表next[i]的數值。
1、字首表建構
aabaabaaf 的字首表為 0101234501，第8位的最長相等前字尾為aabaa，是以長度為5。
2、建構流程
那麼最後一位的我們通過列前字尾表知道是1，但是他的原理是什麼呢？我們字首表本位的值應該是由前一位推得的，由本例得到，第六位的字首表值為4，那麼代表着字元串的前4個字元是能夠在字元串内找到相同的子串。其中索引 0-3 為aaba，索引3-6位aaba。
那麼後一位的字首值應該是多少呢？其實可以看到隻要str[4] == str[7]的時候，那麼我們的字首表值next[7] = next[6]+1。也就是代表着str字元串的[0:4] 和 [3:7]是相同的。
但是，當我們以此類推到str[8]的時候，next[8]應該為多大呢？我們知道，前一位的值表示str的前五個字元是能夠找到重複的，由于我們需要找str[0:8]的最長相等前字尾，那麼首先檢視str[5] ？= str[8] 。
不相同。我們可以确定，這一位的最長相等前字尾的長度一定是小于5的，同時next[8]<=next[4]+1，我們有知道str[4]的最長相等前字尾長度next[4]=2，如果str[2] == str[8]那麼，next[8] = next[1]+1。
發現還是不相同，也就是代表着str[8]沒有最長相等前字尾了next[8]=0。
總結
我們需要求的next[i]的值，肯定需要由next[i-1]來确定，因為最長相等前字尾長度中的字尾長度如果大于等于1，那麼一定包含前一位str[7:8] = “af”，是以疊代往前回退，再往前回退的過程中，每一次的回退過程都代表着next[i]可能的最大長度。隻要回退後的str[next + 1] == str[i]那麼，最長相等前字尾的長度也就出來了。由這個結論類推，我們在做比對的時候，例如str
我們隻需要回退到前一位的最長前字尾長度的位置。
如果str指針的指向和s指針的指向不相同就接着回退，如果相同那麼就接着比對，因為它代表的是s[2]前面的字元已經比對過了。
next字首表實作方法
void getNext(int *next, const string s) {
int j=0; //代表最長相等前字尾的長度
next[0] = 0; //字首表首位為0
int n = s.size();
for(int i=1; i<n; i++) { //從第二位開始往後更新next數組值
while(j>0 && s[i]!=s[j]) j = next[j-1];
if(s[i]==s[j]) j++;
next[i] = j;
}
}
strstr()
void getNext(int *next, const string s) {
int j=0;
next[0] = 0;
int n = s.size();
for(int i=1; i<n; i++) {
while(j>0 && s[i]!=s[j]) j = next[j-1];
if(s[i]==s[j]) j++;
next[i] = j;
}
}
int strStr(string haystack, string needle) {
int next[needle.size()];
getNext(next, needle);
int n = haystack.size();
int j=0; //字首表中比對的長度。
for(int i=0; i<n; i++) {
while(j>0 && haystack[i]!=needle[j]) j=next[j-1]; //如果比對不上，那麼j所表示的長度也需要回退。
if(haystack[i] == needle[j]) j++;//按位比對，如果比對成功那麼就将比對的長度+1。
if(j == needle.size()) return i - j + 1; //j等于待比對字元串的長度時，表示比對結束。
}
return -1;
}