【优选算法】—— 字符串匹配算法

在本期的字符串匹配算法中，我将给大家带来常见的两种经典的示例：

• 1、暴力匹配（BF）算法
• 2、KMP算法

目录

（一）暴力匹配（BF）算法

1、思想

2、演示

3、代码展示

（二）KMP算法

1、思想

2、演示

1️⃣ BF和KMP的区别

 2️⃣  K 的值求解

3️⃣ 求next数组的练习

3、代码展示

4、next数组的优化

（三）总结

---

（一）暴力匹配（BF）算法

1、思想

1. 就是将目标串S的第一个字符与模式串T 的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；
2. 若不相等，则比较S的第二个字符和 T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

2、演示

大家看到上诉这段话时肯定是晦涩难懂的，需要例子支持

• 假定我们给出字符串 ”ababcabcdabcde”作为主串， 然后给出子串： ”abcd”；
• 现在我们需要查找子串是否在主串中出现，出现返回主串中的第一个匹配的下标，失败返回-1 

•  只要在匹配的过程当中，匹配失败，那么：i回退到刚刚位置的下一个,j回退到0下标重新开始

3、代码展示

int BF(char *str,char *sub) //str:主串 sub:子串
{
    assert(str != NULL && sub != NULL);
    if(str == NULL || sub == NULL)
    {
        return -1;
    }
 
    int i = 0;
    int j = 0;
    int strLen = strlen(str);
    int subLen = strlen(sub);
 
    while(i < strLen && j < subLen)
    {
        if(str[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {
            //回退
            i = i-j+1;
            j = 0;
        }
    }
 
    if(j >= subLen)
    {
        return i-j;
    }
 
    return -1;
}
int main()
{
    printf("%d\n",BF("ababcabcdabcde","abcd"));
    printf("%d\n",BF("ababcabcdabcde","abcde"));
    printf("%d\n",BF("ababcabcdabcde","abcdef"));
    return 0;
}

（二）KMP算法

1、思想

2、演示

1️⃣ BF和KMP的区别

 j 的回退位置