28. Implement strStr()

case1(KMP):

1. 两个指针 i，j 分别指向母串 h 和子串 n
2. 如果 h[i] == n[j] 则母串和子串同时开始移动下标进行比值
3. 如果不相等 i 归为上一次母串和子串相等的下标 + 1，j 则归为 0
4. 当 i 或 j 大于母串子串的长度的时候，跳出循环
5. 根据 j 的值判断结果

   class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        i , j = 0 , 0
        h = list(haystack)
        n = list(needle)
        while i < len(h) and j < len(n):
            if h[i]==n[j]:
                i += 1;
                j += 1;
            else:
                i = i - j + 1
                j = 0
        if j == len(needle):
            return i - j
        return -1
   

case2：

1. 循环求解
2. 使用 list 切片

   class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if needle == "":
            return 0
        h = list(haystack)
        n = list(needle)
        for i in range(len(h)):
            if h[i] == n[0] and h[i: len(n) + i] == n:
                return i
        return -1
   

594 (lintcode) Implement strStr function in O(n + m) time.

strStr return the first index of the target string in a source string. The length of the target string is m and the length of the source string is n.
If target does not exist in source, just return -1.

class Solution:
    """
    @param: source: A source string
    @param: target: A target string
    @return: An integer as index
    """
    def strStr2(self, haystack, needle):
        if haystack == None or needle == None:
            return -1
        #generate next array, need O(n) time
        i, j, m, n = -1, 0, len(haystack), len(needle)
        next = [-1] * n
        while j < n - 1:  
            #needle[k] stands for prefix, neelde[j] stands for postfix
            if i == -1 or needle[i] == needle[j]:   
                i, j = i + 1, j + 1
                next[j] = i
            else:
                i = next[i]
        #check through the haystack using next, need O(m) time
        i = j = 0
        while i < m and j < n:
            if j == -1 or haystack[i] == needle[j]:
                i, j = i + 1, j + 1
            else:
                j = next[j]
        if j == n:
            return i - j
        return -1

参考链接：
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
https://leetcode.com/problems/implement-strstr/discuss/13237/Java-and-Python-solution-using-KMP-with-O(m-%2B-n)-time-complexity