strStr 13

Question

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Clarification

Do I need to implement KMP Algorithm in a real interview?

Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first.

Example

If source = "source" and target = "target", return -1.

If source = "abcdabcdefg" and target = "bcd", return 1.

Challenge

O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Solution

这道题很简单，可以遍历第一个string的字符，看以该字符为起点的字符串能否和第二个string匹配，如果不能，则每次向后一位继续寻找。这样的时间复杂度是O(mn)。

而这种字符串匹配的题目经典的方法是用KMP(Knuth-Morris-Pratt)算法，这种算法的时间复杂度是O(m+n）。具体分析可以参考【经典算法】——KMP，深入讲解next数组的求解。

这里再额外解释一下在求next数组时，为什么要求P[0]···P[k-1]这个子串中最大相同前后缀。其实是因为P[k]和P[q]失配，导致之前的最长前后缀必然要缩小来看有没有可能在之后能够使得P[k]和P[q]匹配。因此，我们其实要减少的是P[q-k] ··· P[q-1]，看看在其之间有没有一个位置j使得P[j]...p[q-1]和P[0]...P[k'-1]为新的最长前后缀并且P[k']和P[q]能够匹配。但是因为P[q-k] ··· P[q-1]与P[0] ···P[k-1]相同（之前的最长前后缀），因此上面说的对P[0] ···P[k-1]字串作用得到的结果一样，所以我们要求P[0]···P[k-1]这个子串中最大相同前后缀，其实背后的本质是求P[q-k] ··· P[q-1]这个子串中最大相同前后缀。

代码如下：

public class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack == null || needle == null || needle.length() > haystack.length()){
            return -1;
        }

        if(needle.length() == 0){
            return 0;
        }

        // int res = -1;
        // for(int i = 0; i < haystack.length(); i++){
        //     if(haystack.length() - i >= needle.length() && haystack.charAt(i) == needle.charAt(0)){
        //         res = i;
        //         int pos = i + 1;
        //         for(int j = 1; j < needle.length(); j++){
        //             if(haystack.charAt(pos++) != needle.charAt(j)){
        //                 res = -1;
        //                 break;
        //             }
        //         }
        //     }

        //     if(res != -1){
        //         return res;
        //     }
        // }

        // return res;

        //KMP
        int n = haystack.length();
        int m = needle.length();
        char[] orig = haystack.toCharArray();
        char[] target = needle.toCharArray();
        int[] next = getNextArray(target);
        int q, p;
        for(q = 0, p = 0; q < n; q++){
            while(p > 0 && orig[q] != target[p]){
                p = next[p - 1];
            }

            if(orig[q] == target[p]){
                p++;
            }

            if(p == m){
                return q - m + 1;
            }
        }

        return -1;
    }

    private int[] getNextArray(char[] target){
        int len = target.length;
        int[] next = new int[len];
        next[0] = 0;
        int k = 0;

        for(int i = 1; i < len; i++){
            while(k > 0  && target[i] != target[k]){
                k = next[k - 1];
            }

            if(target[i] == target[k]){
                k++;
            }

            next[i] = k;
        }

        return next;
    }
}