10年专注网络游戏产品质量有保 售后7×24小时服务
24小时咨询热线:4006666666
联系我们
网络游戏有限公司
全国免费服务热线:4006666666
地址 :中国·北京
联系人:陈经理
您的位置: 首页>>热门话题>>正文
热门话题

[不同题选项怎么对齐]匹配失败时,重新对齐图案列和主列怎么对齐?

时间:2023-06-04 作者:admin666ss 点击:73次

Sunday算法是一种字符串匹配算法,与KMP算法相比更容易掌握。

有时比KMP更有效率,例如字符串很长。

该文字未出现在模式列中时,直接跳过,模式列移动位数=模式列长1。

否则,移动位数=图案列的长度-该字符出现在图案列最右边的位置。

这三个步骤展示了具体的执行,感觉很抽象。 但总的来说:

一致时从前到后一致。

匹配失败时,重新对齐图案列和主列。

所以现在的问题是,这种重新对齐怎么对齐呢?

将模式设置为esid

由于成功匹配且在第二位中发现了不匹配,因此在主串中查看参与匹配的最低有效字符的下一位,即s。 s也在图案列中出现过,所以要排队

 [不同题选项怎么对齐]匹配失败时,重新对齐图案列和主列怎么对齐? 热门话题

定位后,正常继续匹配,发现第一名不同,匹配失败。 同样,看v的话,如果v没有出现在图案列中,图案列就会与v后面的e对齐

 [不同题选项怎么对齐]匹配失败时,重新对齐图案列和主列怎么对齐? 热门话题

同样,匹配失败了。 把I排齐

 [不同题选项怎么对齐]匹配失败时,重新对齐图案列和主列怎么对齐? 热门话题

终于,匹配成功了!

 [不同题选项怎么对齐]匹配失败时,重新对齐图案列和主列怎么对齐? 热门话题

是的,Sunday算法也有next数组,需要预处理。

next数组包含模式列中不同字符的最右边下标。

因此,对于上述例子图案列esid

所有英语字符都位于ASCII中,共有256个,因此创建256大小的数组

这样的预处理是用时间来换取空间的

一致的代码用思想写就可以了,有趣的是:

图案列中未出现的字符的next值为-1,因此,正好对齐时图案列往往会向后移动一个数量级。


相关推荐

发表评论