17.1 Implement strStr()

Implement strStr().

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

https://leetcode.com/problems/implement-strstr/

Hint:

Let us first think about a simpler problem. How do you find out if 2 strings are equal?

Implementing strstr is just plain simple simulation.

Consider every index i for the answer. Find if the following 2 strings are equal:

1) Needle string and,

2) String haystack from index i with length the same as needle’s length

Note that the complexity of this solution is O(M*N) where M is length of haystack and N is length of needle.

If you are feeling more adventurous, try solving it in O(M).

Hint: KMP Algorithm*

Below code is from internet, not validate yet.

O(M*N)

public class Solution {
    public int strStr(String haystack,String needle) {

        if(haystack.equals(needle) ||needle.equals("")) {
            return 0;
        }
        int hN, nN;
        hN = haystack.length();
        nN = needle.length();

        int R = 256;
        int dfa[][] = new int[nN + 1][R];
        dfa[0][needle.charAt(0)] = 1;
        int X = 0;

        for (int i = 1; i < nN; i++) {
            for (int r = 0; r < R; r++) {
                dfa[i][r] = dfa[X][r];
            }
            dfa[i][needle.charAt(i)] = i + 1;
            X = dfa[X][needle.charAt(i)];
        }

        X = 0;
        for (int i = 0; i < hN; i++) {
            X = dfa[X][haystack.charAt(i)];
            if (X == nN)
                return i - nN + 1;
        }
        return -1; 
    }  
}

KMP Algorithm

O(M+N)

KMP is good for non English letters, such as DNA sequence (like TGCTGCTGCTGCTCTCCGGG)

BMA is good for English.

public class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null)
            return 0;

        if (needle.length() > haystack.length())return -1;
        if (needle.length() == 0)return 0;

        int[] lps = lspTable(needle);

        int i = 0;

        while (i <= haystack.length() - needle.length()) {
            int success = 1;
            for (int j = 0; j < needle.length(); 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 - lps[j - 1];
                    break;
                }
            }
            if (success == 1)
                return i;
        }

        return -1;
    }
    public static int[] lspTable(String needle){

        int[] lsp=new int[needle.length()];
        lsp[0]=0;

        for(int i=1;i<needle.length();i++){
            int j=lsp[i-1];
            while(j>0 && needle.charAt(i)!=needle.charAt(j)){
                j=lsp[j-1];
            }
            if(needle.charAt(i)==needle.charAt(j)){
                j++;
            }
            lsp[i]=j;
        }
        return lsp;
    }
}