【LeetCode】Day12

28.实现strStr()函数

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

对于本题而言，当 needle 是空字符串时我们应当返回 0 。

python字符串内置函数

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

官方：

暴力解法

def strStr(haystack, needle):
    n = len(haystack)
    m = len(needle)
    #n-m+1理解为i+m<=n,即保证起码当前字符串有m长度，要不然直接就不匹配
    for i in range(0,n-m+1):
        flag = True
        for j in range(0,m):
            #当判断第一个字符时，j =0，相当于haystack[i]与needle[j]比较，如果相同则j = j+1
            #这个时候i，j同时往后移一位，即比较第二个字符，直到j超出m;
            #[i+j]实现了指针在两个字符串中同时移动
            if haystack[i+j] != needle[j]:
                flag = False
                break
            j +=1
            if flag:
                return i
    return -1

res = strStr("hello","ll")
print(res)

KMP算法 ：

        KMP 算法是一个快速查找匹配串的算法，它的作用其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。

        KMP 之所以能够在 O(m + n)O(m+n) 复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。

其他人的讲解（比较好理解）：KMP算法

链接：leetcode官方解答