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

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

- 阅读剩余部分 -