# Implement strStr()

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

## Solution

``````public class Solution {
public int strStr(String haystack, String needle) {
for (int i = 0; ; i++) {
for (int j = 0; ; j++) {
if (j == needle.length()) return i;
if (i + j == haystack.length()) return -1;
if (needle.charAt(j) != haystack.charAt(i + j)) break;

}
}
}
}
``````

KMP 算法在面试的时候不大可能当场写对，所以考虑用 BM 算法 http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140

``````public class Solution {
public int strStr(String haystack, String needle) {
int hlen = haystack.length();
int nlen = needle.length();
int[] jump = new int[256];  // hashmap char-> index, assume ASCII
for(int i=0; i<jump.length; i++) {
jump[i]=-1;
}
for(int i=0; i<nlen; i++) {
jump[needle.charAt(i)] = i; // index of last occurrence
}
int skip=0;
for(int i=0; i<hlen-nlen+1; i+=skip) { // !!! not i<hlen
skip=0;
for(int j=nlen-1; j>=0; j--) {
if(haystack.charAt(i+j)!=needle.charAt(j)) {
skip =Math.max( 1, j-jump[haystack.charAt(i+j)] );
// max is j+1, min is 1 (do not allow <0);
break;
}
}
if(skip==0) return i;
}
return -1;
}
}
``````