字符串匹配: KMP算法, BM_BC, BM_GS算法

字符串匹配是搜索算法的基础,也是数据结构中一个十分有用的算法分支,我在学习KMP和BMBC算法的时候就觉得听的云里雾里,但经过一些实操和分析不难发现,这几个算法都是很好理解,并且对算法有很务实启发的。

以下我从零开始梳理以下如何建立一个清晰,并且有一定模式的理解这两个算法的思路。


1. 什么是字符串匹配

从一个字符串中查询是否完全包含另一个字符串的过程。如果有则返回起始位置,无则匹配失败。 例: 在 "这是一个多美丽又遗憾的世界" 匹配 "美丽" 应该返回5. 匹配"太美丽" 失败。

前菜开始:


2. 直观解法 循环遍历

令 字符串 S = "这是一个多美丽又遗憾的世界" 模式串(待匹配子串) s = "美丽" 循环遍历S并且在每一次S[i]与 s[j=0]匹配时,依次比较 S[i++] 与 s[j++], 若成功则可以返回当前的 i-j 即为第一个字符所在的位置,失败则 i = i-j,再右移1位继续比较。

* 边界情况,当 i> m-n 时,宣告失败。 也就是说剩余可以配的元素已经不足够了,无需比较即告失败。 另外,约定查找失败时,返回-1;

算法示例:

int matchStr( char * S, char * s )
{
    size_t m = strlen(S), n = strlen(s);
    int i =0, j = 0;
    while( i < m-n+1 && j<n ){
        if( S[i] == s[j] ){
            i++;j++;
        }else{
            i -= j-1; // i = i-j+1
            j = 0;
        }
    }
    return j==n ? i-j : -1;
    // 当且仅当j与n相等时,模式串最后一位匹配成功
}
循环遍历的方式有什么问题呢? 那就是机械,无论如何都需要完整遍历S,并且每一次至少需要比对1次,而从渐进角度来说总体来说复杂度是达到O(m*n)。

接下来才是正餐:


3. 优化方向/算法策略

优化的可能性仔细分析一下,就是如何减少没必要的匹配。 首先我们看一下,模式串都有哪些可能性呢? (这里只需要考虑前缀,因为如果不是前缀重复,发生失配的时候一定是要从第一位开始比较的)

1 . 真前缀永不重复

a b c d e f g

2 . 单元素真前缀重复 / 真·一元前缀字串 重复

a a a a b c a a e

3 . 真·多元前缀字串重复

a b c a b c a b c a a b

那么接下来,分别看一下这几种不同的模式串,分别有怎样的优化方式。

1. 不重复

S: x x x x a b c x x d e f g x x
s: a b c d e f g

1: a
2:   a
3:     a
4:       a
5:         a b c d
6:

前5次的时候,由于首字符均不匹配所以直接跳过了后续字符。 在不考虑算法的情况下,你觉得6应该怎么比对 才是最合理的呢?

在i=5的时候,我们已经比对了abc成功,这个时候表示S里刚匹配过的局部串一定不会是aaa aab,对吧?

所以如果我们只是往后移动一个格子,不免显得有点迟钝了。

S: x x x x a b c x x d e f g x x

5:         a b c d
6:           a      无意义匹配
6:             a    无意义匹配
6:               a

所以这个规律就是,当模式串没有重复非空字串时,匹配失败时应该直接将 模式串s与当前匹配失败的位置 对齐。 * 当不重复元素越长,失败时可以直接跳过的距离也就越大。

2. 单元素重复

2.1 失配在重复元素上

S: x x a a a c x a a a a b c x 
s: a a a a b c a a e

1: a
2:   a
3:     a a a a
4:           a a
4:       a a a 

这里问题又来了,我们应该选用哪一个4号方案呢? 很显然,我们应该让a,直接对到c。

和第一种情况类似,发生失配的位置必然不可能和先前的元素匹配,所以应该直接对齐至最初元素。

2.2 失配在非重复元素上

S: x x a a a a b a a a a b c x 
s: a a a b c

1: a
2:   a
3:     a a a b
4:           a a
4:       a a a b

这个时候我们发现,就不能直接快速跳过了。 这里的原因是什么呢? 我们把其中失配的 a,b 替换成 c,b 就会发现原因了。

S: x x a a a c b a a a a b c x 
s: a a a b c

1: a
2:   a
3:     a a a b
4:           a
4:       a a a

这时,由于C并不在s的前缀中,所以失配的时候再比较也是没有意义的,而a属于s前缀,所以不能排除移位之后匹配的可能。

这里的结论是,当S串中的失配的元素不在重复子串中的时候(在1,2中就是首元素),直接和首元素对齐快速跳过。

S: a a a a b a a a a
s: a a a a a

1: a a a a a         // 快速跳过
2:           a a a a

S: a a a a b a a a a
s: a b c

1: a b
2:   a b
3:     a b
4:       a b c
5:         a  
6:           a b

3. 多元素重复

3.1 失配在模式串之外的元素上

S: x x a a b c a c c a a b c x 
s: a b c a b c a b c a a b 

1: a
2:   a
3:     a b
4:       a b c a b
5:

3.2 失配在模式串已有的元素上

文章地址:




标签: c++, algorithm, 字符串匹配, KMP, BM_BC, BM_GS

添加新评论