当前位置: 首页 > news >正文

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,主串向前移动,子串立即重置

http://www.lqws.cn/news/212383.html

相关文章:

  • 【Zephyr 系列 13】BLE Mesh 入门实战:构建基础节点通信与中继组播系统
  • 【C++】类型转换
  • 死锁的四个必要条件
  • HTML面试整理
  • 在Mathematica中使用Newton-Raphson迭代绘制一个花脸
  • 【判断既约分数】2022-4-3
  • Python60日基础学习打卡Day46
  • 杭州瑞盟 MS35774/MS35774A 低噪声256细分微步进电机驱动,用于空调风门电机驱动,香薰电机驱动
  • 【HarmonyOS5】UIAbility组件生命周期详解:从创建到销毁的全景解析
  • 智能手表供应链与采购清单(Aurora Watch S1)
  • 用队列实现栈
  • [TI板]MSPM0G3507学习笔记(一) 超详细keil环境配置+烧录配置+空工程迁移+vscode配置+点灯
  • 容器安全最佳实践:云原生环境下的零信任架构实施
  • 游戏(game)
  • 【RTSP从零实践】1、根据RTSP协议实现一个RTSP服务
  • compose 组件 ---无ui组件
  • SDC命令详解:使用set_propagated_clock命令进行约束
  • 路过美国Intel公司
  • 【AI论文】反思、重试、奖励:通过强化学习实现大型语言模型的自我提升
  • 计算机组成原理-存储器的概述
  • 关于datetime获取时间的问题
  • stm32内存踩踏一例
  • Doris 与 Elasticsearch:谁更适合你的数据分析需求?
  • 实战:子组件获取父组件订单信息
  • 快速上手shell脚本运行流程控制
  • 行为设计模式之Command (命令)
  • 嵌入式知识篇---Zigbee串口
  • 基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
  • 大话软工笔记—需求分解
  • RT-Thread内核组成——内核移植