題目
mplement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
方法一：
解題思路：
普通的算法思路很簡單，直接兩個(gè)指針遍歷就ok了，但是效率一般招狸，比較出名的是KMP算法。
代碼：
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null)
return -1;
int i = 0;
int j = 0;
while (i < haystack.length() && j < needle.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
return j == needle.length() ? i - j : -1;
}
方法二：
解題思路：
利用KMP算法求解老速，這種方法不太容易理解，可以參考下面給出的鏈接凸主。
代碼：
public int[] getNext(String pattern) {
int next[] = new int[pattern.length() + 1];
int i = 0;
int j = -1;
next[i] = j;
while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else
j = next[j];
}
return next;
}
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null)
return -1;
int next[] = getNext(needle);
int i = 0;
int j = 0;
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else
j = next[j];
}
return j == needle.length() ? i - j : -1;
}
