28. 实现 strStr()-一一网

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

输入：haystack = "hello", needle = "ll"
输出：2
复制代码

解法一

暴力解法 遍历haystack字符串，使haystack中所有与needle字符串长度相等的子串都匹配一遍。

def strStr1(haystack, needle):
    """暴力解法"""

    m, n = len(haystack), len(needle)
    for i in range(m - n + 1):  # i 可以等于 m-n, 所以这里需要 +1
        flag = True  # 记录子串是否相等，默认为True
        for j in range(n):
            if haystack[i + j] != needle[j]:  # 如果有一个字符不相等，就说明子串不相等，退出循环
                flag = False
                break
        if flag: return i  # 如果循环结束，flag还是为True，说明子串相等，此时的i就是起始位置
    return -1  # 如果循环结束，还是没有，就说明没有匹配的子串，直接返回 -1
复制代码

复杂度分析

时间复杂度：m 为原串的长度，n 为匹配串的长度。其中枚举的复杂度为 $O(m−n)$ ，构造和比较字符串的复杂度为 $O(n)$ 。整体复杂度为 $O((m−n)∗n)$ 。
空间复杂度： $O(1)$ 。

解法二

KMP算法 实际上是对上面暴力解法的优化。

主要思想： 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

具体的过程分析请看(对于没有KMP经验的人，这几个讲解比较容易理解)：

「代码随想录」KMP算法详解

帮你把KMP算法学个通透！（理论篇）

帮你把KMP算法学个通透！（求next数组代码篇）

def strStr2(haystack, needle):
    """KMP算法 前缀表（不减一）实现"""

    def getNext(s):
        """求s的next数组，也就是s各个位置对应的前缀表"""
        nex = ['' for _ in range(len(s))]  # 初始化next数组
        j = 0  # j 指向前缀末尾
        nex[0] = 0  # 初始化第一位的值，因为字符串的第一位的前后缀的长度都为0
        for i in range(1, len(s)):  # i 指向后缀末尾，从1开始，前后缀末尾才能比较
            while j > 0 and s[i] != s[j]:  # j 要保证大于0，因为下面有取j-1作为数组下标的操作
                # 当前后缀末尾不相同时，意味着前后缀的相同长度不能再 +1
                # 并且等于前一位的前后缀最大相同长度，即前一位的回退位置
                j = nex[j - 1]
            if s[i] == s[j]:
                j += 1  # 当前后缀末尾相同时，意味着前后缀的相同长度再 +1
            nex[i] = j  # 对数组进行赋值，j就是s[0:i]字符串的前后缀的最长相同长度
        return nex

    # 特殊情况判断
    if not needle: return 0

    m, n = len(haystack), len(needle)
    nex = getNext(needle)  # 获取needle的前缀表
    j = 0  # 表示指向needle的下标，默认从0开始
    for i in range(m):  # i表示haystack的下标 就从0开始，遍历haystack字符串
        while j > 0 and haystack[i] != needle[j]:
            # 当出现不匹配时，j就等于前一个位置的前后缀的最长相同长度，即前缀表中的值
            # 即j就跳到最长前缀的下一位，重新开始匹配
            j = nex[j - 1]
        if haystack[i] == needle[j]:
            # 当匹配时，继续比较下一位，j和i同时向右移动一位，i的增加在for循环里面
            j += 1
        if j == n:
            # 当j等于n时，表示文本串haystack里已经出现了模式串needle，返回needle的起始位置
            return i - n + 1
    return -1  # 上面的遍历结束，还没有出现模式串needle，说明不存在，返回-1
复制代码