leetcode Implement strStr()

タイトル
mplement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
方法1:
問題解決の考え方:
普通のアルゴリズムの構想はとても簡単で、直接2つのポインタは遍歴してokになって、しかし効率は普通で、比較的に有名なのはKMPアルゴリズムです.
コード:

public int strStr(String haystack, String needle) {  
    if (haystack == null || needle == null)  
        return -1;  
  
    int i = 0;  
    int j = 0;  
    while (i < haystack.length() && j < needle.length()) {  
        if (haystack.charAt(i) == needle.charAt(j)) {  
            i++;  
            j++;  
        } else {  
            i = i - j + 1;  
            j = 0;  
        }  
    }  
    return j == needle.length() ? i - j : -1;  
} 

方法2:
問題解決の考え方:
KMPアルゴリズムを用いて解くと,この方法はあまり理解しにくく,以下に示すリンクを参照できる.
コード:

public int[] getNext(String pattern) {  
    int next[] = new int[pattern.length() + 1];  
    int i = 0;  
    int j = -1;  
    next[i] = j;  
    while (i < pattern.length() - 1) {  
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {  
            i++;  
            j++;  
            next[i] = j;  
        } else  
            j = next[j];  
    }  
    return next;  
}  
  
public int strStr(String haystack, String needle) {  
    if (haystack == null || needle == null)  
        return -1;  
    int next[] = getNext(needle);  
    int i = 0;  
    int j = 0;  
    while (i < haystack.length() && j < needle.length()) {  
        if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {  
            i++;  
            j++;  
        } else  
            j = next[j];  
    }  
    return j == needle.length() ? i - j : -1;  
}

参照リンク:
http://kb.cnblogs.com/page/176818/