Problem: 28. 找出字符串中第一个匹配项的下标
思路
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
解题方法
- 可以使用 Python 内置的字符串方法 find() 来实现这个功能。find() 方法返回子字符串在字符串中第一次出现的位置，如果没有找到则返回 -1。
- KMP算法
复杂度
时间复杂度:
O(N*M)，其中 N 是字符串 haystack 的长度，M 是字符串 needle 的长度。在最坏的情况下，即 needle 与 haystack 的每个子串都几乎相同，但最后一个字符不匹配时，需要对 haystack 的每个位置都尝试匹配 needle，并且每次匹配都需要比较 M 个字符。
空间复杂度:
O(1)。使用 find() 方法进行搜索不需要额外的存储空间，所需空间不随输入数据的大小而改变，因此是常数级别的。
代码
class Solution(object):
def strStr(self, haystack, needle):
return haystack.find(needle)
使用KMP算法（目前能力还看不懂）
class Solution(object):
def strStr(self, haystack, needle):
if not needle:
return 0
def build_lps(pattern):
lps = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = lps[j - 1]
if pattern[i] == pattern[j]:
j += 1
lps[i] = j
return lps
lps = build_lps(needle)
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = lps[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - j + 1
return -1
KMP算法的时间复杂度为O(N+M)，其中N是haystack的长度，M是needle的长度
