算法笔记：substring-two pointer系列

例1：leetcode 28. Implement strStr()

solution-github
Time complexity: O(n^2)

1. KMP算法是解决这个算法很标准的方法，要问清楚数据量,小数据量没必要用KMP
2. 这个题经常在电面中出现
3. 如果真的问KMP怎么办，首先概率很低，另外，换一个更简单的算法Rabin-Karp，跟KMP时间复杂度一样

class Solution {
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    public int strStr(String source, String target){
        if(target=="") return 0;
        if(source==""||source==null||target==null) return -1;
        
        for(int s = 0; s<source.length(); s++){
            int tmp = s;
            int t = 0;
            while(source.charAt(tmp)==target.charAt(t)){
                if(t==target.length()-1) return s;
                tmp++;
                t++;
                if(tmp>source.length()-1) return -1;
            }
        }
        return -1;
    }
}

Rabin-Karp算法解决strStr

111484879948_.pic副本.jpg
121484879950_.pic副本.jpg

public class Solution {
           public int BASE = 100000;

    /**
     * @param source a source string
     * @param target a target string
     * @return an integer as index
     */
    public int strStr2(String source, String target) {
       
       if(source == null|| target==null) return -1;
       int m = target.length();
       if(m ==0) return 0;
       
       int power = 1;
       for(int i = 0; i < m; i++){
           power = (power*31)%BASE;
       } 
       
       int targetHash = 0;
       for(int i = 0; i < m; i++){
           targetHash=(targetHash*31+target.charAt(i))%BASE;
       }
       
       int hashCode = 0;
       for(int i = 0; i<source.length();i++){
           hashCode= (hashCode*31+source.charAt(i))%BASE;
           if(i<m-1) continue;
           if(i>=m){
               hashCode=hashCode-(source.charAt(i-m)*power)%BASE;
               if(hashCode<0){
                   hashCode+=BASE;
               }
           }
           if(hashCode == targetHash){
               if(source.substring(i-m+1,i+1).equals(target)){
                   return i-m+1;
               }
           }
       }
       return -1;
    }   
}

kmp算法，之前知乎看到过一个，讲的不太清楚，这个还不错http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

该算法推广到二维，在matrix中找string，可以看StringMatch2D
tips：
Time Complexity of String.substring()
It was O(1) in older versions of Java. However, this has actually changed started with Java 7. The char[] sharing was eliminated, and the offset and length fields were removed. Now substring() just copies all the characters into a new String.
Ergo, substring is O(n) in Java 7 update 6.