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数组c语言(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(m−n)O(m−n复杂度剖析)，构造和比较字符串的复杂度为 $O(n)$。整体复杂度为 $O((m-n)\ast n)$。
• 空间复杂度：O(1)O(1)O(1算法的时刻复杂度取决于)。

解法二

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

首要思维： 当呈现字符串不匹配时，能够记载一部分之前复杂度排序现已匹配的文本内容，运用这些信息防止算法从头再去做匹配。

具体的进程剖析请看(关于没有KMP阅历的人，这几个讲解比较简单了解)：

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

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

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

def strStr2(haystack, needle):
"""KMP算法 前缀表（不减一）完毕算法工程师和程序员差异"""
def getNext复杂度o(1)什么意思(算法的时刻复杂度取决于s):
"""求s的next数组，也就是s各个方位复杂度对应的前缀表"""
nex = ['' fo算法导论r _ in range(len(s))]  # 初始化next数组
j = 0  # j 指向前缀完毕
nex[0] = 0  # 初始数组指针化第一位的值，由于字符串的第一位的前后缀的长度都为0
for i in range(1, len(s)):  # i 指向后缀完毕，从1开始，前后缀完毕才华比较
wh复杂度怎样核算的ile j &复杂度符号gt; 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 ne复杂度最优x
# 特殊情况判别
if not needle: ret复杂度ourn 0
m, n = len(haystack), len(n算法的有穷性是指ee复杂度怎样核算的dle)
nex = getNext(needle)  # 获取need算法le的前缀表
j = 0  # 标明指向needle的下标数组和链表的差异，默许从0开始
for i in range(m):  # i标明hays复杂度剖析tack的下标 就从0开始，遍历haystack字符串
while j > 0 and haystack[i] != n数组去重eedle[j]:
# 当呈现不匹配时，j就等于前一个方位的前后缀的最长相同长度，即复杂度排序前缀表中的值
# 即j就跳到最长前缀的下一位，从头开始匹配
j = nex[j - 1]
if haystack[i] == needle[j]:
# 当匹配时，数组词持续比较下一位，j和i一起向右移动一位，i的增加在for循环里面
j += 1
i复杂度of j == n:
# 当j等于n时，标明文本串haystack里现已呈现了方法串needle，回来needle的开始方复杂度o位
return i - n + 1
retur数组排序n -1  # 上面的遍历完毕，还没有呈现方法串needle，阐明不存在，回来-1

复杂度剖析

• 时刻复杂度：$O(n+m)$，其间 n 是字符串 haystack 的长度，m复杂度o 是字符串 need数组函数的运用方法le 的长度。咱们至多需求遍历两字符算法的时刻复杂度取决于串一次。
• 空间复杂度：$O(m)$，其间 m 是字符串 ne数组词edle 的数组函数的运用方法长度。咱们只需求保存字符串 needle 的复杂度o前缀函数。

力扣官方答案