2023/11/2

从KMP算法看strStr()的实现+java注解

首先要明确KMP算法的目的：匹配失败后，不需要再次从模式串的首字符开始匹配，即跳过一定数量的前缀字符

这时就需要从模式串下手，模式串是在匹配过程中始终不变的，当匹配失败发生时，模式串指针前的模式字符一定与原字符一致，因此需要看前一个字符(当前字符是失败字符)的前缀表值，而前缀表值是最大前后缀相等长度，为什么？想想目的：匹配失败后，不需要再次从模式串的首字符开始，那么我们需要跳过一定数量的前缀字符，那为什么要看后缀字符与前缀的相等数量？

因为后缀字符是离原字符串失败字符最近的，后缀与前缀有多少个字符相等，我就能跳过多少个前缀字符

前缀表记录的，就是当前字符“匹配后”与前缀相等的字符数，即能跳过的前缀字符数量(也就是应当跳到的索引)

KMP精讲8

上图实际为PM表，真正的next表:PM表右移一位，第一位补-1，就是next表

next的实现实际上有套娃

搞两个指针(整数)，第一个快指针先走，每次与慢指针+1比较，如果一致，则慢整数+1，若匹配失败，则执行回滚：慢指针j指向next的j（因为前缀字符记录的也是相对后缀重复的个数，也能跳过部分字符）

#include "string"

using namespace std;

class Solution {
public:
    void getNext(int *next, string &s) {
        int j = -1; //j永远小一点
        next[0] = -1;
        for (int i = 1; i < s.size(); i++) {
            while (j >= 0 && s[i] != s[j + 1]) { //回滚,由于i会先加1，所以这里要判断i是否等于j+1
                j = next[j];
            }
            if (s[j + 1] == s[i]) {
                j++;
            }
            next[i] = j;
        }
    }

    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);

        //匹配的过程其实就是创建next的过程
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 回滚，同上
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

java学习

每日杂谈2023.11.2

新开栏目，用来记录自己的生活点滴，美好的回忆与哲理的思考一样都应当被记录

顺便记录最近对自己的情绪影响最大的一些事件

1、这下成超人了，2公里9min10s，现在速度竟然能和中考时期比肩了，主要还是提高步频的训练法比较有效

2、追番：葬送的芙莉莲

很好的作品，堪比魔法少女小圆、mygo、死亡笔记、寄生兽，t0级别，寿命论只是这层作品的最浅层，

t0是啥？大概就是拥有完整的世界观、人物刻画细致、矛盾冲突引人深思吧，关键她还作画精致、op是yasobi、ed是milet唱的，我简直嗨到不行

t1级的大概就是进击的巨人、咒术回战这样的吧，无法引导人进行深度哲理思考，对了，夏日重现估计也算(其作画和bgm也很精美，可惜引人思考的地方并不多)

3、大物期中考试

哎哎，大物；服了，最后一题2分钟写完考完过了一会才反应过来写错了，C!

还有就是，自己其实努力了还挺久，但结果配不上努力啊！！课外做了一堆，结果就考课内的习题，还考得很综合…

尽管罗老师的混合式命定论在尝试阻止我emo，但结果配不上努力，这种落差，果然对现在的我来说，还是难以接受啊…..（可能我还年轻

4、既搞深度学习又要学算法还要学java果然对我这种效率低下的人还是太极限了，哎哎，关键我转专业还一堆课，还顺便打了个bit杯

但其实时间充分利用的话也不是不可能（

一心多用，是否能成功呢？

5、最近没咋打游戏了，塞尔达上次玩也是半个月前了吧….

游戏瘾就这样戒掉了？

LOADING