28. Implement strStr

有两个条件需要注意，一个是h - n + 1，也就是两个字串需要比较的长度，如果该值小于0，直接返回-1。另一个是while (k < n && haystack.charAt(j) == needle.charAt(k))条件不能颠倒。k指针指向的位置必须小于needle字符串的长度，才能和haystack中的j指针比较，防止循环内部的指针改变使得while条件语句溢出，如["a", ""]这个例子。

时间复杂度O(n^2)

public int strStr(String haystack, String needle) {
    int h = haystack.length(), n = needle.length();
    for (int i = 0; i < h - n + 1; i++) {
        int k = 0;
        int j = i;
        while (k < n && haystack.charAt(j) == needle.charAt(k)) {
            j++;
            k++;
        }
        if (k == n) return i; // needle如果是空字符串在这边会直接return 0..

    }
    return -1;
}

kmp

# https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    A, B= len(haystack), len(needle)
    if not B: return 0
    lps = self.create_lps(needle)
    i, j = 0, 0
    while i < A:
        if haystack[i] == needle[j]:
            i += 1
            j += 1
        if j == B:
            return i - j
        if i < A and haystack[i] != needle[j]:
            if j:
                j = lps[j - 1]
            else:
                i += 1
    return -1


def create_lps(self, needle):
    # For the pattern “AABAACAABAA”, 
    # lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
    length = len(needle)
    lps = [0] * length
    dis, i = 0, 1
    while i < length:
        if needle[i] == needle[dis]:
            dis += 1
            lps[i] = dis
            i += 1
        elif dis:
            dis = lps[dis - 1]
        else:
            lps[i] = 0
            i += 1
    return lps