一、BF算法

1.什么是BF算法

BF 算法也称为暴力匹配算法。它可以从目标字符串的第一个字符开始，也可以指定主串中查找的起始位置pos逐个与模式字符串进行匹配。如果不匹配，则目标字符串的匹配位置向后移动一位，重新开始与模式串的比较。

2.图形分析

（1）主串S从第一位开始，主串S与模式串T的前两位都匹配成功，但S的第三位是a而T是c，第一次匹配失败，i值加一，j值退回到起始位置1。

（2）主串从第二位开始，主串S字母是b，与模式串第一位a不同，匹配失败，i值加一，j值退回到起始位置1。

（3）重复匹配步骤，直到字串T与主串S完全匹配。

 简单来说，就是主串的每一个字符作为子串的开头，与模式串进行匹配。对主串做大循环，每个字符再做一个模式串T长度的小循环，知道匹配成功为止或全部遍历完成。

3.代码实现

//返回主串S和模式串T匹配的第一个字符的位置pos
int Index_BF(string S, string T, int pos)
{
    int j = 1;//j用于模式串中当前位置的下标值
    int i = pos;//i用于主串S中当前位置的下标值，从pos位置开始匹配
    while (i <= S[0] && j <= T[0])//字符串的[0]一般表示的是字符串长度，也可以用length（）函数计算得到
    {
        if（S[i] == T[j])//相等则继续比较
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;//i退回到上次匹配首位的下一位
            j = 1;//j值回溯到模式串首位
        }
    }
    if（j > T[0])//匹配成功
        return i - T[0];//返回pos位置
    else//匹配失败
        return 0;
}

4.时间复杂度分析 

在最好情况下，模式串在主串的起始位置就完全匹配。

1. 分析过程：

   • 此时只需要比较一次主串和模式串的第一个字符，发现匹配后，继续比较后续字符，由于模式串在主串起始位置完全匹配，所以总共只需要比较模式串的长度（记为 m）次。
   • 例如，主串为 “ABCDEFG”，模式串为 “ABC”，第一次比较主串和模式串的第一个字符‘A’，匹配成功后继续比较，很快发现整个模式串在主串起始位置完全匹配。

2. 时间复杂度：

   • 最好情况下的时间复杂度为 O (m)，其中 m 为模式串的长度。

在最坏情况下，模式串在主串的最后位置才完全匹配，或者主串中根本不存在模式串。

1. 分析过程：

   • 对于每一个主串中的字符，都需要与模式串进行比较，每次比较失败后，主串的比较位置向后移动一位，然后重新开始与模式串的比较。
   • 主串长度为 n，模式串长度为 m。每次比较都需要比较 m 个字符，而总共可能进行 n - m + 1 次比较。
   • 例如，主串为 “AAAAAB”，模式串为 “AB”，首先比较主串的第一个‘A’和模式串的第一个‘A’，匹配成功后继续比较第二个字符，发现不匹配，主串比较位置向后移动一位，再次从主串的第二个‘A’和模式串的第一个‘A’开始比较，如此反复，直到最后在主串的最后位置才找到模式串。

2. 时间复杂度：

   • 最坏情况下的时间复杂度为 O (nm)，其中 n 为主串的长度，m 为模式串的长度。

平均情况下的时间复杂度分析较为复杂，需要考虑主串和模式串中字符的分布情况等因素。

1. 分析过程：

   • 假设主串中每个位置与模式串匹配的概率相同，且每次比较失败后，主串的比较位置向后移动一位。
   • 在平均情况下，大约需要比较 n/m 次才能找到匹配，每次比较需要 m 次字符比较，所以平均时间复杂度为 O (nm)。

2. 时间复杂度：

   • 平均情况下的时间复杂度也接近 O (nm)。

综上所述，BF 算法的时间复杂度在最好情况下为 O (m)，在最坏情况和平均情况下为 O (nm)，其中 n 为主串的长度，m 为模式串的长度。

二、KMP算法

1.什么是KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

2.图形分析

（1）第一种例子

如果主串S为"abcdefgab"，模式串T为"abcdex"，如果用BF算法的话，我们会发现他们前五个字符完全相同，直到第六位不等，按照BF算法又会从主串S的i=2，3，4，5，6开始匹配。如图

 我们会发现这②~⑤完全是没必要的步骤，因为b不可能与a相等，c也不可能与a相等，这些步骤完全可以省略，只需保留①⑥步骤即可。如图

之所以保留⑥，是因为①中已经知道S[6]≠T[6]，但并不能保证S[1]≠T[6]。

（2）第二种例子

如果主串S为"abcababca"，模式串T为"abcabx"，我们发现主串Si从1~5都与模式串T相同，只有i=6时不同，又注意到如果模式串子串中有于主串首字符相等的字符也是可以省略一部分没必要的步骤，因为模式串T的首位a与第四位a相等，第二位b与第五位b相等，所以i=4与i=5步骤可以省略，如图

 通过观察，我们发现i值不回溯，需要考虑的就是j的值了。在上面我们提到了模式串T的首字符与自身后面的字符作比较，如果有相同字符，j值的变化就会不相同，就是说j值的变化与主串S并没有关系，而取决于当前字符之前的串的前后缀的相似程度。因此我们引进了一个数组next用来定义各个位置j值的变化，next数组的长度就是模式串T的长度。

3.next数组的推导

例如：T="ababaaaba"

                        j       123456789

            模式串T       ababaaaba

                next[j]       011234223

①当j=1时，next[1]=0;

②当j=2时，j由1到j-1就只有字符"a"，属于其他情况next[2]=1；

③当j=3时，j由1到j-1串是"ab"，"a"与"b"不等，属于其他情况next[3]=1；

④当j=4时，j由1到j-1串是"aba",前缀字符"a"与后缀字符"a"相等，所以next[4]=2；

⑤当j=5时，j由1到j-1串是"abab",前缀字符"ab"与后缀字符"ab"相等，所以next[5]=3；

⑥当j=6时，j由1到j-1串是"ababa",前缀字符"aba"与后缀字符"aba"相等，所以next[6]=4；

⑦当j=7时，j由1到j-1串是"ababaa",前缀字符"a"与后缀字符"a"相等，所以next[7]=2；

⑧当j=8时，j由1到j-1串是"ababaaa",前缀字符"a"与后缀字符"a"相等，所以next[8]=2；

⑨当j=9时，j由1到j-1串是"ababaaab",前缀字符"ab"与后缀字符"ab"相等，所以next[9]=3；

根据观察可以得到，如果前后缀一个字符相等，next[j]值为2，两个字符相等为3，所以n个字符相等next[j]值就是n+1。

4.代码实现

//返回模式串的next数组
void get_next(string T, int* next)
{
    int i=1, k=0;
    next[1] = 0;
    while (i < T[0])//T[0]表示字符串长度
    {
        if (k == 0 || T[i] == T[k])
        {
            i++;
            k++;
            next[i] = k;
        }
        else
        {
            k = next[k];//若字符不相等，则k值回溯
        }
    }
}

 5.next数组的改进

 5.1图例

如果模式串连续几个都是相同的字符，你会发现j值的回溯是一步一步退回去的，比如主串"aaabce"，模式串"aaax"，如图

 我们发现②③④步骤都是多余的，因为"a"与"b"肯定是不等的。那么可以用首个相同的字符的next的值去取代与它相同字符的next的值。

5.2next数组的优化推导

例如：T="ababaaaba"(不相等维持原值)

                        j       123456789

            模式串T       ababaaaba

                next[j]       011234223

           nextval[j]       010104210

①当j=1时，nextval[1]=0;

②当j=2时，因为第二个字符"b"的next值为1，而第一个字符是"a"，不相等，维持原值1，nextval[2]=next[2]=1；

③当j=3时，因为第三个字符"a"的next值为1，而第一个字符是"a"，相等，nextval[3]=nextval[1]=0；

④当j=4时，因为第四个字符"b"的next值为2，而第二个字符是"b"，相等，nextval[4]=nextval[2]=1；

⑤当j=5时，因为第五个字符"a"的next值为3，而第三个字符是"a"，相等，nextval[5]=nextcal[3]=0；

⑥当j=6时，因为第六个字符"a"的next值为4，而第四个字符是"b"，不相等，维持原值4；

⑦当j=7时，因为第七个字符"a"的next值为2，而第一个字符是"b"，不相等，维持原值2；

⑧当j=8时，因为第八个字符"b"的next值为2，而第二个字符是"b"，相等，nextval[8]=nextval[2]=1；

⑨当j=9时，因为第九个字符"b"的next值为3，而第三个字符是"a"，相等，nextval[9]=nextval[3]=0；

5.3代码实现

//求模式串的next数组的修正值存入数组nextval
void get_nextval(string T, int* nextval)
{
    int i = 1, k = 0;
    nextval[1] = 0;
    while (i < T[0])//T[0]表示字符串长度
    {
        if (k == 0 || T[i] == T[k])
        {
            i++;
            k++;
            if (T[i] != T[k])//当前字符与前缀字符不同
            {
                nextval[i] = k;
            }
            else
            {
                nextval[i] = nextval[k];//将前缀字符的nextval的值赋给nextval在i位置的值
            }
        }
        else
        {
            k = nextval[k];//若字符不相等，则k值回溯
        }
    }
}

6.KMP算法实现

 有了next数组后，我们就可以实现KMP算法了，具体代码如下

//返回子串T在主串S中出现的位置pos，不存在返回0
void Index_KMP(string S,string T, int pos)
{
    int i = pos;
    int j=1;
    int next[81];//定义next数组
    get_next(T, next);//调用函数得到next数组
    while (i <= S[0] && j <= T[0])
    {
        if (j == 0 || S[i] == T[j])//与BF比增加了j==0的比较，如果两个字符相等就继续
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];//j退回到合适位置重新匹配，i值不变
        }
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}

7.时间复杂度分析构建 next 数组的时间复杂度

1. • 在 KMP 算法中，首先需要构建模式字符串的 next 数组。这个过程的时间复杂度为O(m) ，其中m是模式字符串的长度。
   • 构建 next 数组的过程是通过对模式字符串进行自匹配来实现的。具体来说，对于模式字符串的每个位置i ，需要找到以位置 i-1 结尾的最长相同前缀和后缀的长度，然后将这个长度作为 next [i] 的值。
   • 这个过程可以通过一个循环来实现，循环的次数与模式字符串的长度m相等，因此构建 next 数组的时间复杂度为O(m) 。

2. 字符串匹配的时间复杂度

   • 在使用 KMP 算法进行字符串匹配时，时间复杂度主要取决于模式字符串和文本字符串的长度。
   • 假设文本字符串的长度为n，模式字符串的长度为m 。在匹配过程中，每次比较字符时，如果字符不匹配，就可以根据 next 数组的值直接将模式字符串向右移动一定的距离，而不需要回溯文本字符串的指针。
   • 由于在匹配过程中，文本字符串的指针最多只会移动 n次，而模式字符串的指针最多只会移动 m次，因此字符串匹配的时间复杂度为O(n+m) 。

三、总结 

在效率方面KMP算法肯定是优于BF算法的，但是BF算法更加简单直观，容易理解，比较容易实现；KMP 算法的实现相对复杂，需要理解部分匹配表的计算和使用方法。总之，如果对效率要求不高，或者字符串长度较小，可以使用 BF 算法。如果需要处理大规模字符串匹配问题，或者对效率有较高要求，应使用 KMP 算法。