408第一季 - 数据结构 - 字符串和KMP算法
闲聊
这章属于难点但考频低
3个名词记一下：模式匹配，主串，字串（模式串）
举个例子 主串 aabaaaabaab
字串 aabaab
模式匹配 从主串找到字串
暴力解法
也是不多说
很暴力就是了
KMP算法
next数组
它只和字串有关
先标注一下-1和0，然后我们要求b的next数组
就这样看看重叠的是否相同，这里是相同的，且只有1位，所以这里b下面是1
然后我们求下标为3的a，这里是要重叠的完全相同，很显然ab和aa不相同
然后我们要往右移动，发现b和a依旧不相同，再往右移就没了，所以下标a next数组是0
然后就很熟练了，然后是接下来的2个
下标为4的a next数组是1
下标为5的b next数组是2
最后会变成
꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱小练习꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱
a b c a c next数组是什么呀
没错，是-1 0 0 0 1
꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱小练习꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱꒰ঌ( ⌯' '⌯)໒꒱
使用！
然后就是使用了，怎么用
我们可以看见第一次对比时，主串和字串到下标为5的时候不一样了
然后对应的我们找下标为5的next数组，发现是2，对应是下标为2
把下标为2移动到下标为5的地方，就成了下面第三行的地方
然后这个方法能保证前面相等，也就是你可以看见aa和aa是一样的
这个方法也可以瞬间移动三步，不需要一步一步往右移了
向右平移的距离为 i - next[i]
当然你也可以看见，主串的指针不一样，字串的指针根据next回退，这里指向next = 2的位置
做题区
1
c
2
b
-1的含义是？
饿啊，这里第一个就不一样了，而且next数组居然是-1，太难受，怎么办
于是，这里主串就要动了，子串重置到主串指针那，就是字串的第一个指向主串指针那
传说级KMP算法
就是进一步优化
我们可以看见第一次c和b不一样时，通过next数组到下标为2的b，准备移动，但我们本来就知道主串那明明是c啊，你移动到字串下标为2的地方依然是个b，你这不白白比较一次吗
下面是next的一步到位形态
怎么去理解呢
第一个a(下标为0)依旧是-1
第二个a(下标为1)通过next数组到第一个a(下标为0)，发现第一个a(下标为0)的next是-1，于是就把第二个a(下标为1)的next数组更新为-1
第一个b(下标为2)通过next数组发现是第二个a(下标为1)，但a和b不一样，无法判断接下来的a是不是多余的比较，所以b不变还是1
后面就不用多说了第三个a(下标为3)的next指向第一个a(下标为0)，一样是a，本是同根生，更新下标为-1
......
可以看见一步到位了，多移了一格
做个题先
当你到下标为4的a时，next数组是-1，主串向前移动，子串立即重置