字符串匹配算法

暴力算法

以主串中每一个字符作为开头,与模式串进行比较。复杂度O(mn)

特点是比较的时候主串和模式串的指针都前移,失败后主串和模式串的指针都后移。

KMP算法

image
当B和C匹配失败的时候,之前的匹配一定是成功的,也就是说主串失败点B之前一定是ABCA,那么下一次匹配的时候可以直接将模式串A与主串中第二个A对齐,然后从主串失败点B继续匹配。

根据这个原理可以预先计算一个next表:

失败时模式串的字符 A B C A C
- 1 1 1 2

当失败在模式串C处,查表得next值为2,也就是从模式串的第二个位置继续匹配。

实际匹配过程中动的只有指针,主串指针从左向右依次移动,没有后退没有跳跃。模式串指针则根据next表进行跳跃。复杂度为O(n+m)

BM算法

image
先比较主串最后一个字符B与模式串最后一个字符F,匹配失败,我们知道如果要匹配成功,主串中B也一定与模式串中b匹配,而模式串后面一大段都没有“B”,所以可以快速将模式串移动到两个B对齐的位置。
根据这个原理可以预先计算一个bc表:

失败时主串的字符 A B C D E F H I J K L
1 2 3 4 5 6 0 0 0 0 0

我们同样可以预先计算一张bc表,当匹配失败时可以查表快速移动。这种策略通常从后向前比较,因为大多数的字符串匹配不成功的概率比匹配成功的概率大,所以从后向前比较效率更高。

BM算法同样兼顾KMP算法的思想,不过BM算法是从后向前匹配,所以需要生成一个倒着的next表,称之为gs表。

BM算法每当匹配失败时,分别查bc表和gs表,取这两个表中移动最快的值。

匹配过程中主串指针有跳跃的情况,这就说明它的效率可以超过线性。最好的情况复杂度为O(n/m),最坏情况为O(n+m)

posted @ 2021-07-20 20:43:43
评论加载中...

发表评论