LeetCode 28 - Implement strStr()

String Replace - Linkedin
Implement strStr() | N00tc0d3r
The strstr function locates a specified substring within a source string. Strstr returns a pointer to the first occurrence of the substring in the source. If the substring is not found, strstr returns a null pointer.

public String strStr(String haystack, String needle)

X. KMP
https://www.programcreek.com/2012/12/leetcode-implement-strstr-java/

        if(haystack==null || needle==null)    
            return 0;
 
 int h = haystack.length();
 int n = needle.length();
 
 if (n > h)
  return -1;
 if (n == 0)
  return 0;
 
 int[] next = getNext(needle);
 int i = 0;
 
 while (i <= h - n) {
  int success = 1;
  for (int j = 0; j < n; j++) {
   if (needle.charAt(0) != haystack.charAt(i)) {
    success = 0;
    i++;
    break;
   } else if (needle.charAt(j) != haystack.charAt(i + j)) {
    success = 0;
    i = i + j - next[j - 1];
    break;
   }
  }
  if (success == 1)
   return i;
 }
 
 return -1;
}
 
//calculate KMP array
public int[] getNext(String needle) {
 int[] next = new int[needle.length()];
 next[0] = 0;
 
 for (int i = 1; i < needle.length(); i++) {
  int index = next[i - 1];
  while (index > 0 && needle.charAt(index) != needle.charAt(i)) {
   index = next[index - 1];
  }
 
  if (needle.charAt(index) == needle.charAt(i)) {
   next[i] = next[i - 1] + 1;
  } else {
   next[i] = 0;
  }
 }
 
 return next;
}

https://eugenejw.github.io/2017/07/leetcode-28

    public int strStr(String haystack, String needle) {
        int[] kmpTable= new int[needle.length()];
        buildKMPTable(needle, kmpTable);
        int i = 0;
        int j = 0;
        int N = haystack.length();
        int M = needle.length();
        while (i < N && j < M) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                if (++j == M) {
                   return i - j;
                } 
            } else {
                if (j == 0) {
                    i++;
                }
                else{
                    j = kmpTable[j-1];
                }
            } 
        }
        if (M == 0)   return 0; // when needle is null
        return -1;
    }
    private void buildKMPTable(String needle, int[] kmpTable) {
        int j = 0;
        int i = 1;
        while (i < kmpTable.length) {
            if (needle.charAt(i) == needle.charAt(j)) {
                kmpTable[i++] = ++j;
            } else {
                if (j == 0){
                    kmpTable[i++] = 0;
                } else {
                    j = kmpTable[j-1];
                }
            }
        }       
    }

http://yyeclipse.blogspot.com/2013/02/leetcode-implement-strstr-string.html
Rolling Hash Algorithm
Here's a simple example of rolling hash.
Input: char array A[1...10]. Length k=5.
H[1..5] = A[1]*a^4 + A[2]*a^3 + A[3]*a^2 + A[4]*a^1 + A[5]*a^0
Then how can we compute H[2..6] ?
Instead of computing it from scratch, we can do as following based on H[1..5]
1. Remove first item of H[1..5] :  H[2..6] = H[1..5] - A[1]*a^4
2. Times constant a                  :  H[2..6] *= a
3. Add  last item A[6]              :  H[2..6] += A[6]

public class StrStrRollingHash {
    public static final int A = 3;
   
    public String strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if(m==0)
            return haystack;
        if(n<m)
            return null;
       
        char[] input = haystack.toCharArray();
        int needleHash = getHash(needle.toCharArray(),0,m-1);
        int haystackHash = getHash(input,0,m-1);
       
        for(int i=0;i<n-m;i++){
            if(haystackHash==needleHash){
                if(haystack.substring(i, i+m).equals(needle))
                    return haystack.substring(i);
            }
            //rolling hash
            haystackHash-=(int)(input[i]*Math.pow(A, m-1));//remove i th item
            haystackHash*=A;//times A
            haystackHash+=input[i+m];//add i+m th item
        }
       
        if(haystackHash==needleHash){
            if(haystack.substring(n-m, n).equals(needle))
                return haystack.substring(n-m);
        }
       
        return null;
       
    }
   
    private static int getHash(char[] array,int start,int end){
        int k=end-start;
        int sum=0;
        for(int i=start;i<=end;i++){
            int item = (int)(array[i]*Math.pow(A,k--));
            sum+=item;
        }
        return sum;
    }
https://chazyhabit.wordpress.com/2014/07/16/implement-strstr-leetcode-7/

    public String strStr(String haystack, String needle) {

        if(haystack==null || needle==null||haystack.length()<needle.length()) return null;

        if(needle.length()==0) return haystack;

        int base = 29;

        long needleHash = 0;

        long tempBase = 1;

        // get the hashcode for the needle

        for(int i=needle.length()-1; i>=0; i--){

            needleHash += (long) needle.charAt(i) * tempBase;

            tempBase *= base;

        }

        long hayHash = 0;

        tempBase = 1;

        // get the hashcode for the first substring of haystack

        for(int i=needle.length()-1; i>=0; i--){

            hayHash += (long) haystack.charAt(i) * tempBase;

            tempBase *= base;

        }

        tempBase /= base;

        // check the first substring

        if(hayHash == needleHash) return haystack;

        // traverse the rest substring, get hashcode and check

        for(int i=needle.length(); i<haystack.length(); i++){

            hayHash = (hayHash - (long) haystack.charAt(i-needle.length()) * tempBase) * base + (long) haystack.charAt(i);

            if(hayHash == needleHash){

                return haystack.substring(i-needle.length()+1);

            }

        }

        return null;

    }

Brute Force:
https://discuss.leetcode.com/topic/18839/elegant-java-solution

    public int strStr(String s, String t) {
        if (t.isEmpty()) return 0; // edge case: "",""=>0  "a",""=>0
        for (int i = 0; i <= s.length() - t.length(); i++) {
            for (int j = 0; j < t.length() && s.charAt(i + j) == t.charAt(j); j++)
                if (j == t.length() - 1) return i;
        }
        return -1;
    }

https://discuss.leetcode.com/topic/9872/share-my-accepted-java-solution

    public int strStr(String haystack, String needle) {
        int l1 = haystack.length(), l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        }
        int threshold = l1 - l2;
        for (int i = 0; i <= threshold; ++i) {
            if (haystack.substring(i,i+l2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }

http://www.matrix67.com/blog/archives/115

public int strStr(String haystack, String needle) { if(haystack==null || needle==null) return 0;   if(needle.length() == 0) return 0;   for(int i=0; i<haystack.length(); i++){ if(i + needle.length() > haystack.length()) return -1;   int m = i; for(int j=0; j<needle.length(); j++){ if(needle.charAt(j)==haystack.charAt(m)){ if(j==needle.length()-1) return i; m++; }else{ break; }   } }   return -1; }

http://vivianjiang12.blogspot.com/2012/09/leetcode-implement-strstr.html
public String strStr(String haystack, String needle) {
     if(needle.length() == 0) return haystack;
   
     int n = 0;
   
     for(int i = 0; i <= haystack.length() - needle.length(); i++){
         n = 0;
       
         while(n < needle.length() && haystack.charAt(i+n) == needle.charAt(n))
              n++;
             
         if(n == needle.length()) return haystack.substring(i);
     }
   
     return null;
}

X.
https://leetcode.com/problems/implement-strstr/discuss/12807/Elegant-Java-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;
    }
  }
}

https://leetcode.com/problems/implement-strstr/discuss/12811/Share-my-accepted-java-solution

    public int strStr(String haystack, String needle) {
        int l1 = haystack.length(), l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        }
        int threshold = l1 - l2;
        for (int i = 0; i <= threshold; ++i) {
            if (haystack.substring(i,i+l2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }