1 题目：
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.
2 思路：
估计是要实现KMP算法。
正好我从大二就开始想把它看懂。。。
这次搞明白了。
我是 谷歌 “KMP 通俗”，前面有三个帖子，看完后，差不多才懂得。
3 代码：
/* KMP method */
//
public int strStr(String haystack, String needle) {
// pre handle
if( needle.length()==0){
return 0;
}
if(haystack.length()==0){
return -1;
} char[] target = haystack.toCharArray();
char[] point = needle.toCharArray(); // build the point array, the last feature[len-1] not satify the sub-prifix & sub-suffix rule, but not matter,the feature[len-1] will not be use
Integer[] feature = new Integer[needle.length()];
feature[0] = 0;
for(int i=1; i<needle.length()-1; i++){
if(point[i]!=point[feature[i-1]]){
feature[i] = 0;
}else{
feature[i] = feature[i-1]+1;
}
} // search
int j = 0;
for(int i=0; i<haystack.length();){
if(target[i]==point[j]){
j++;
if(j == needle.length()){
// match, return index
return i-j+1;
}
i++;
}else{
if(j == 0){
/* j=0 not match,i++ */
i++;
}else{
/* not match, continue to compare target[i] */
j = feature[j-1];
}
}
} return -1;
}