Implement strStr() LeetCode

最简单的方法是brute force，直接逐个扫描。时间复杂度为O（mn）这里n是字符串长度，m是pattern的长度。Code如下：

public String strStr(String haystack, String needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(haystack == null || needle == null) return null;
        if(needle.length()==0) return haystack;
        int hLen = haystack.length();
        int nLen = needle.length();
        if(hLen < nLen) return null;
        for(int i=0; i<hLen; i++){
            int j=i;
            //适当的剪枝
            while(nLen+i <= hLen && j<hLen && haystack.charAt(j) == needle.charAt(j-i)){
                j++;
                if(j-i == nLen) return haystack.substring(i);
            }
        }
        return null;
    }

优化解法，肯定是要用到KMP(Knuth-Morris-Pratt)，中心思想是利用每次已经match的字符串信息来做优化。我找到一个ppt，做了适当的修改。
具体的讲解可以参考这个中文博客：http://blog.csdn.net/lin_bei/article/details/1252686
搞了个PPT也可以看下

Code如下

public String strStr(String haystack, String needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
      if(needle.length()==0) return haystack;
      int hLen = haystack.length();
      int nLen = needle.length();
   
      if(hLen < nLen) return null;
   
      int[] next = new int[nLen];
      getNext(needle, next);//O(m)space for storing the next position
      int i=0, j=0;
      while(i<hLen && j<nLen){
          if(haystack.charAt(i)==needle.charAt(j)){
              if(j==needle.length()-1) return haystack.substring(i-j);
              ++i;
              ++j;
          }else{
              if(j==0)i++;
              else j=next[j];
          }
      }
return null;
}

private void getNext(String str, int[] next){
   if(str.length()==0 || str.length()==1) return;
   int start = 0;
   int index = 2;
 
   while(index < str.length()){
       if(str.charAt(index-1)==str.charAt(start)){
           next[index++]=++start;
       }else if(start>0){
           start = next[start];
       }else{
           next[index++]=0;
       }
   }
 
}