字符串匹配： 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

添加新评论