Paste_Image.png

My code:

public class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null)
            return -1;
        if (needle.length() == 0)
            return 0;
        int[] next = getNext(needle);
        int j = 0;
        int i = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            else
                j = next[j];
        }
        if (j == needle.length())
            return i - j;
        else
            return -1;
    }
    
    private int[] getNext(String needle) {
        int[] next = new int[needle.length()];
        int k = -1;
        int j = 0;
        next[0] = -1;
        while (j < needle.length() - 1) {
            if (k == -1 || needle.charAt(k) == needle.charAt(j)) {
                k++;
                j++;
                if (needle.charAt(k) != needle.charAt(j))
                    next[j] = k;
                else
                    next[j] = next[k];
            }
            else
                k = next[k];
        }
        return next;
    }
    
    public static void main (String[] args) {
        Solution test = new Solution();
        System.out.println(test.strStr("mississippi", "a"));
    }
}

My test result:

这道题目要求是用KMP算法来做的。具体KMP算法是什么东西，就看这篇博客吧。
讲的太详细了。
http://blog.csdn.net/v_july_v/article/details/7041827

KMP 算法的核心，或者是难点，就是构造next[] 数组。
一旦next[] 数组构造好了，主程序很好写。
那么， next[] 数组的难点是什么。关键在于理解。
next[j] 是什么意义呢？
意义是， 在 [0, j - 1] 这个区域内，string needle 的最大前缀后缀相等长度。
也就是说， next[] 数组求解过程中，
是通过 next[j - 1] 来求 next[j]， 当等于j时，此时要求的又是 next[j + 1]了。
所以， j < needle.length() - 1
因为当j = needle.length() - 2 时， 就可以求出 next[needle.length() - 1] 了。

然后还需要理解一些概念。
next[j] = 0; 是什么含义。
代表在 [0, j - 1] 这段区域内，string needle 没有重复的前缀后缀，随意，
直接拿 haystack[i] 与 needle[0] 进行比较了。相当于，在 i 处失配时，直接将字符串needle头部直接移动到i处。重新进行匹配。

那么 next[j] = -1 是什么含义呢？
代表， haystack[i] 也不等于 needle[0], 即，在i处失配时，甚至都不需要将needle头部与i开始的字符串重新进行匹配了，直接跳过i，和i + 1处开始的字符串进行重新匹配。
这就是改进版的KMP，将next[] 优化了。

而且求 next[] 数组时，

while (j < needle.length() - 1) {
            if (k == -1 || needle.charAt(k) == needle.charAt(j)) {
                k++;
                j++;
                if (needle.charAt(k) != needle.charAt(j))
                    next[j] = k;
                else
                    next[j] = next[k];
            }
            else
                k = next[k];
        }

一开始我在想，在needle和haystack匹配到很长时，如果此时失配，那么k = next[k]，这时再次失配呢？没关系，那么就再次进行循环。
因为在这个过程中，j是不变化的，k是不断往后倒退的。直到找到符合的情况。
这就是一种递归啊。用while体现出来的一种递归思想，更科学的应该称为，迭代？

还有就是优化next的代码，多了这么一段。

if (needle.charAt(k) != needle.charAt(j))
    next[j] = k;
else
    next[j] = next[k];

我在想，在needle和haystack匹配到很长时，如果此时下一个继续匹配了，但是检测出，
needle.charAt(k) == needle.charAt(j)
那么我们需要执行这个操作，
next[j] = next[k];
那我们一定可以保证，
needle.charAt(k) != needle.charAt(next[j]) 吗？
一定可以保证的。
因为我们是从0 开始 往后填充next[]的，我们一步步往前走，保证每一步的
needle.charAt(k) != needle.charAt(next[j])
所以一直递归到后面，是可以保证的。
很像是那个 科学证明法，从1开始证明，到后面，都理所当然了。

KMP就总结到这里了。

**
总结： String， KMP
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public int strStr(String haystack, String needle) {
        String s = haystack;
        String p = needle;
        if (s == null || p == null) {
            return -1;
        }
        else if (p.length() == 0) {
            return 0;
        }
        
        int[] next = getNext(p);
        int i = 0;
        int j = 0;
        while (i < s.length() && j < p.length()) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            }
            else {
                if (j == 0) {
                    i++;
                }
                else {
                    j = next[j];
                }
            }
        }
        if (j >= p.length()) {
            return i - p.length();
        }
        else {
            return -1;
        }
    }
    
    private int[] getNext(String p) {
        int[] dp = new int[p.length()];
        dp[0] = -1;
        int k = -1;
        int j = 0;
        while (j < dp.length - 1) {
            if (k == -1 || p.charAt(k) == p.charAt(j)) {
                k++;
                j++;
                dp[j] = k;
            }
            else {
                k = dp[k];
            }
        }
        return dp;
    }
}

又把 KMP算法看了一遍，希望这次别再忘了。
其实就是 DP

Anyway, Good luck, Richardo! -- 09/20/2016