leetcode刷题之路：28. 找出字符串中第一个匹配项的下标

刷算法题：

第一遍：1.看5分钟，没思路看题解

2.通过题解改进自己的解法，并且要写每行的注释以及自己的思路。

3.思考自己做到了题解的哪一步，下次怎么才能做对(总结方法)

4.整理到自己的自媒体平台。

5.再刷重复的类似的题目，根据时间和任务安排刷哪几个板块

6.用c++语言 都刷过一遍了 就刷中等

一.题目

给你两个字符串 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 仅由小写英文字符组成

二、反思

1.自己的解法

这题我记得当时数据结构的时候老师影影约约说过是什么算法，挺出名的，我直接选择网上找答案，没有重新思考了，然后才知道这是大名鼎鼎的kmp算法。看下面题解。

2.题目的解法 

def kmp_search(string,patt):#输入子串和主串
    next = build_next(patt)#假设我们已经算出了next数组
    i=0 #主串中的指针
    j=0 #子串中的指针
    while i<len(string):#只遍历一次主串
        if string[i]==patt[j]:#如果字符匹配，两个指针后移
            i+=1
            j+=1
        elif j>0:  #字符失配，根据next跳过子串前面的一些字符。
            j=next[j-1]
        else:     #子串第一个字符就失配
            i+=1
 
        if j==len(patt): #匹配成功
            return i-j
 
def build_next(patt):#输入子串
    """
    计算next数组
    """
    next=[0]
    prefix_len=0 #当前共同前后缀的长度
    i=1#i只会增加 直到i等于子串长度 相当于此时子串计算的进度。
    while i<len(patt):
        if patt[prefix_len]==patt[i]:#子串i位置和前后缀位置匹配
            prefix_len+=1#前后缀加一
            next.append(prefix_len)#存储前后缀
            i+=1
        else:#如果匹配不上
            if prefix_len==0:#如果是新出现的字母
                next.append(0)
                i+=1
            else:#如果不是新出现的字母
                prefix_len=next[prefix_len-1]#这里就是视频中最难理解的地方
#当匹配不上又不是出现的新字母，那就是要重新跟新一下最小前后缀。
    return next

 【最浅显易懂的 KMP 算法讲解】 https://www.bilibili.com/video/BV1AY4y157yL/?share_source=copy_web&vd_source=40f272f9fffd74275782be314ad10bc9

以上代码是出自这个视频，建议理解kmp的思路后再来看代码，尤其是next数组这里

 3.思路的异同

好好看，好好学

三.进步的地方

假期去实习了，最大的感受就是不好找工作，很卷，算法题是不可避免的，想去参加acm或者蓝桥杯，即便已经大三了，还是想去参加。最近有时间除了准备项目，也在看几个比较经典的算法，快速排序和归并排序等，慢慢来吧，然后就尽量考研，考好一点的学校，考不上好学校，读本小的话我还是选择工作。想了很久...........也不知道未来的自己会怎么看待这个决定呢