题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

我的解法——双循环（AC）

两层循环
时间空间复杂度均为O(mn)。
Beat37%

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if(len(haystack) - len(needle) < 0):
            return -1
        
        for i in range(len(haystack) - len(needle) + 1):
            flag = True
            for j in range(len(needle)):
                if(haystack[i + j] != needle[j]):
                    flag = False
                    break
            if(flag):
                return i
        return -1

最优解法——KMP算法

参考讲解：
- 清华大学邓俊辉：http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184_2X+sp/courseware/4c294e9ea5b5433d831443e64f64bacb/5c4a944aba1f4c9e996f555f7f9b76cb/
- https://blog.csdn.net/v_july_v/article/details/7041827

def strStr(self, haystack, needle):
    if haystack == None or needle == None:
        return -1
    m, n = len(haystack), len(needle)
    
    #generate next array, need O(n) time
    i, j = -1, 0
    next = [-1] * n
    while j < n - 1:  
        # needle[i] stands for prefix, neelde[j] stands for postfix
        # 考虑next[j]和next[j + 1]的递推关系
        # 	1.P[i] == P[next[i]]时，next[i + 1] = next[i] + 1
        # 	2.P[i] != P[next[i]]时，i = next[i]，直至满足条件1时套用1，这个序列严格递减，并且必定收敛于next[0] = -1
        if i == -1 or needle[i] == needle[j]:   
            i, j = i + 1, j + 1
            next[j] = i
        else:
            i = next[i]
        print i,j,next[i],next[j]

    #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