28. 实现strStr
方法一:
class Solution {
public int strStr(String haystack, String needle) {
int m = needle.length();
if (m == 0) {
return 0;
}
int n = haystack.length();
if (n < m) {
return -1;
}
int i = 0;
int j = 0;
while (i < n - m + 1) {
while (i < n && haystack.charAt(i) != needle.charAt(j)) {
i++;
}
if (i == n) {
return -1;
}
i++;
j++;
while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
if (j == m) {
return i - j;
} else {
i -= j - 1;
j = 0;
}
}
return -1;
}
}
方法二:KMP
class Solution {
public void getNext(int[] next,String s){
int j = -1;
next[0] = j;
for(int i = 1;i < s.length();i++){
while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
j = next[j];
}
if(s.charAt(i) == s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
public int strStr(String haystack, String needle) {
if(needle.length() == 0){return 0;}
int[] next = new int[needle.length()];
getNext(next,needle);
int j = -1;
for(int i = 0;i<haystack.length();i++){
while(j >=0 && haystack.charAt(i) != needle.charAt(j+1)){
j = next[j];
}
if(haystack.charAt(i) == needle.charAt(j+1)){
j++;
}
if(j == needle.length() - 1){
return i - needle.length() + 1;
}
}
return -1;
}
|