給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開(kāi)始）祷肯。如果 needle 不是 haystack 的一部分，則返回 -1 摹恰。如果needle=""丐重，那么返回0。
解題思路：KMP
(1) 簡(jiǎn)單的解法：設(shè)立雙指針轧葛，一個(gè)指向主串【i】搂抒，一個(gè)指向模式串【j】。每次遇到不匹配時(shí)尿扯，就回溯求晶，移動(dòng)j從頭開(kāi)始匹配。時(shí)間復(fù)雜度：假定主串s的長(zhǎng)度為n衷笋，模式串p的長(zhǎng)度為m芳杏，O(nm)*。
class Solution {
public int strStr(String haystack, String needle) {
int i = 0;
int j = 0;
int n = 0;
while(true){
// 找到了最先出現(xiàn)的needle子串
if(n >= needle.length()) return i;
// 說(shuō)明本次尋找不匹配辟宗，在剛開(kāi)始進(jìn)入時(shí),無(wú)需匹配爵赵。
else if(j > 0){
j = j - n + 1;
n = 0;
}
// 不匹配時(shí)，找到第一個(gè)能與之匹配的下標(biāo)
while(j < haystack.length() && n < needle.length() && haystack.charAt(j) != needle.charAt(n)) j++;
if(j >= haystack.length()) break;
i = j;
// 匹配時(shí)
while(j < haystack.length() && n < needle.length() && haystack.charAt(j) == needle.charAt(n)){
j++;
n++;
}
}
return -1;
}
}
(2) 使用KMP泊脐，存下之前遍歷的信息（next數(shù)組）空幻。? 時(shí)間復(fù)雜度：假定主串s的長(zhǎng)度為n，模式串p的長(zhǎng)度為m容客，O(n + m)氛悬。
指針 i 可以不用回溯，同時(shí)也避免指針 j 從頭再去做匹配耘柱。
● KMP詳解：0. 字符串理論知識(shí) - 簡(jiǎn)書(shū) (jianshu.com)
class Solution {
public int strStr(String haystack, String needle) {
int[] next = new int[needle.length()];
next[0] = 0;
createNext(next, needle);
int i = 0;
int j = 0;
while(i < haystack.length()){
while(j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];
if(haystack.charAt(i) == needle.charAt(j)) j++;
i++;
if(j >= needle.length()) return i - j;
}
return -1;
}
public void createNext(int[] next, String p){
int i = 1;
int j = 0;
while(i < next.length){
// 不匹配時(shí)如捅，回退指針j，直到匹配或j = 0
while(j > 0 && p.charAt(j) != p.charAt(i)){
j = next[j - 1];
}
// 此時(shí)查看是否能匹配上
if(p.charAt(j) == p.charAt(i)){
j++;
}
next[i++] = j;
}
}
}
