408第一季 - 数据结构 - 字符串和KMP算法

宝塔山 · 昨天 14:55

闲聊

这章属于难点但考频低

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

固然你也可以看见，主串的指针不一样，字串的指针根据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，主串向前移动，子串立即重置

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

408第一季 - 数据结构 - 字符串和KMP算法

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块