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

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

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

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

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

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

一致时从前到后一致。

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

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

将模式设置为esid

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

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

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

终于,匹配成功了!

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

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

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

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

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

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

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


发表评论

Copyright 2002-2022 by 尔韵网络游戏门户网(琼ICP备2022001899号-3).All Rights Reserved.