题解所用知识点:KMP算法
题目已经明确是KMP模板题了......
定义一个数组next
next[i]：b[0~i] 这个子串里，最长相等前后缀的长度
不理解没关系 这么复杂的玩意我也看不懂
举个例子
b = z y z
i=0(字符 z)：只有一个字符，无前后缀 ->nex[0]=0
i=1(zy)：无前缀后缀相等 -> nex[1]=0
i=2(zyz)：前缀z = 后缀z，长度 1 -> nex[2]=1
我对next的理解如就是next数组内存的是从当前位置到b上一个与当前位置相同字符的位置的下标
当然这是错的......气笑了
next[i]存的是长度,不是下标
考虑到有人类无法理解的可能
换一个讲解方式:
已经匹配到 j 位置突然断了：
不用让 j 变回 0 重头来
直接跳到 前面已经能对上的最长那段末尾
这就是 next 数组的作用.
说白了就是提前预处理好从j位置匹配不上后看下一次匹配可以从哪里直接开始
这样就可以节省很多的时间 当然这个预处理如果你没有预处理好......照样TLE哦~
这个代码建议背记下来 实在不行自己理解一遍 确保考场上能自己推出来算你牛逼
啊什么你想让我现在就给你代码.?你想害死我直接说......
代码在题解区自己用AI写一个代码之后再去题解区看得了