【重学数据结构与算法(JS)】字符串匹配算法(四)——Sunda

2020-01-23  本文已影响0人  懒成铁

前言

惯例,最重要的匹配思路还是要贴一遍:

  1. 模式串主串进行比较
    • 从前往后比较
    • 从后往前比较
  2. 匹配时,比较主串模式串的下一个位置
  3. 失配时,
    • 模式串中寻找一个合适的位置
      • 如果找到,从这个位置开始与主串当前失配位置进行比较
      • 如果未找到,从模式串的头部与主串失配位置的下一个位置进行比较
    • 主串中找到一个合适的位置,重新与模式串进行比较

Sunday算法也许是三种里面最好理解也最好写的一种了,它的思路也是在于失配时如何跳过尽可能多的字符,具体的说,主要是优化了第3步,失配时,在主串中找到一个合适的位置,重新与模式串进行比较

算法介绍与分析

栗子

初始状态,i = 0, j = 0, m = 4

QQ20200123-205626.png

比较 S[0]P[0],发现不相等,看 S[4] 处发现并没有在 P 中出现

QQ20200123-205718.png

直接将 P 移至 S[4] 的后一位,此时 i = 5, j = 0, m = 9

QQ20200123-205913.png

比较 S[5]P[0],发现不相等,看 S[9] 处发现有在 P 中出现

QQ20200123-210136.png

P 中的 iS 中的 i 对齐,此时 i = 8, j = 0, m = 12

QQ20200123-210415.png

比较 S[8]P[0],发现不相等,看 S[12] 处发现并没有在 P 中出现

QQ20200123-210651.png

直接将 P 移至 S[12] 的后一位,此时 i = 13, j = 0, m = 17

QQ20200123-210854.png

比较 S[13]P[0],发现不相等,看 S[17] 处发现有在 P 中出现

QQ20200123-211050.png

P 中的 nS 中的 n 对齐,此时 i = 15, j = 0, m = 18

QQ20200123-211352.png

继续匹配,直到 j === plen - 1 = 3,则匹配成功,得到结果 i - j = 18 - 3 = 15

QQ20200123-211750.png

代码实现

极端情况的排除

carbon.png

整体逻辑框架

由此,我们就可以写出整体的框架:

carbon的副本.png

细节的完善

carbon的副本2.png

总结

Sunday算法 遵循匹配思路,失配时采取自己的优化策略,也尽可能的移动了最多的步数,达到提高效率的目的,且易理解。

后记

“字符串匹配算法”是“重学数据结构与算法”系列笔记:

上一篇下一篇

猜你喜欢

热点阅读