Implement strStr()

题目地址：
https://leetcode.com/problems/implement-strstr/description/

题目：

Implement strStr().

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

解题思路：
这道题可以用常规的双指针解法，也可以用KMP解法来解决。

代码：

public class ImplementstrStr {

    public static void main(String[] args){
        ImplementstrStr implementstrStr = new ImplementstrStr();
        String haystack = "abaabcabcabcaa";
        String needle = "abcabcaa";
        int rst = implementstrStr.strStr(haystack, needle);
        System.out.println(rst);
    }

    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return -1;
        }
        int[] kmp = implementKMP(needle);
        int j = 0;
        for(int i = 0; i <= haystack.length() - 1; i++){
            if(haystack.charAt(i) == needle.charAt(j)){
                j += 1;
                if(j == needle.length()){
                    return i - (j - 1);
                }
            }
            else if(j == 0){
                continue;
            }
            else{
                j = kmp[j - 1];
                i -= 1;
            }
        }
        return -1;
    }

    private int[] implementKMP(String needle) {
        char[] chars = needle.toCharArray();
        int[] kmp = new int[needle.length()];
        kmp[0] = 0;
        int i = 1;
        int j = 0;
        while(i <= needle.length() - 1){
            if(chars[i] == chars[j]){
                kmp[i] = j + 1;
                i += 1;
                j += 1;
            }
            else if(j == 0){
                kmp[i] = 0;
                i += 1;
            }
            else{
                j = kmp[j - 1];
            }
        }
        return kmp;
    }
}