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

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

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

  • 1、暴力匹配(BF)算法
  • 2、KMP算法



(一)暴力匹配(BF)算法

1、思想

BF 算法,即 暴力 (Brute Force) 算法 ,是普通的模式匹配算法, BF 算法的思想:

  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;
}

时间复杂度分析:最坏为 O(m*n); m 是主串长度, n 是子串长度


(二)KMP算法

1、思想

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

2、演示

1️⃣ BF和KMP的区别

区别 KMP BF 唯一不一样的地方在,我主串的 i 并不会回退,并且 j 也不会移动到 0 号位置

 首先举例,为什么主串不回退?

 j 的回退位置

💨 针对上述这样的情况,我们就需要引出next数组

KMP 的精髓就是 next 数组:也就是用 next[j] = k;来表示,不同的 j 来对应一个 K 值, 这个 K 就是你将来要移动的 j 要移动的位置。

2️⃣ K 的值求解

  • 1、规则:找到匹配成功部分的两个相等的真子串(不包含本身),一个以下标 0 字符开始,另一个以 j-1 下标字符结尾。
  • 2、不管什么数据 next[0] = -1;next[1] = 0;在这里,我们以下标来开始,而说到的第几个第几个是从 1 开始

3️⃣next数组的练习

练习 1: 举例对于”ababcabcdabcde”, 求其的 next 数组?

到这里大家对如何求next数组应该问题不大了,接下来的问题就是,已知next[i] = k;怎么求next[i+1] = ?

如果我们能够通过 next[i] 的值 , 通过一系列转换得到 next[i+1] 得值,那么我们就能够实现这部分。

那该怎么做呢?

  1. 首先假设: next[i] = k 成立,那么,就有这个式子成立: P0...Pk-1 = Px...Pi-1;得到: P0...Pk-1 = Pi-k..Pi-1;
  2. 到这一步:我们再假设如果 Pk = Pi;我们可以得到 P0...Pk = Pi-k..Pi;那这个就是 next[i+1] = k+1;

那么: Pk != Pi 呢?

 

3、代码展示

void GetNext(int *next,const char *sub)
{
    int lensub = strlen(sub);
    next[0] = -1;
    next[1] = 0;
    int i = 2;//下一项
    int k = 0;//前一项的K
    while(i < lensub)//next数组还没有遍历完
    {
        if((k == -1) || sub[k] == sub[i-1])
        {
            next[i] = k+1;
            i++;
            k++;//k = k+1???//下一个K的值新的K值
        }
        else
        {
            k = next[k];
        }
    }
}
int KMP(const char *s,const char *sub,int pos)
{
    int i = pos;
    int j = 0;
    int lens = strlen(s);
    int lensub = strlen(sub);
    int *next = (int *)malloc(lensub*sizeof(int));//和子串一样长
    assert(next != NULL);
    GetNext(next,sub);
    while(i < lens && j < lensub)
    {
        if((j == -1) || (s[i] == sub[j]))
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    free(next);
    if(j >= lensub)
    {
        return i-j;
    }
    else
    {
        return -1;
    }
}
int main()
{
    char *str = "ababcabcdabcde";
    char *sub = "abcd";
    printf("%d\n",KMP(str,sub,0));
    return 0;
}

4、next数组的优化

next 数组的优化,即如何得到 nextval 数组:有如下串:

  1. aaaaaaaab;
  2. next 数组是-1,0,1,2,3,4,5,6,7

nextval 是:-1, -1, -1, -1, -1, -1, -1, -1, 7

💨  为什么出现修正后的数组,假设在 5 号处失败了,那退一步还是 a,还是相等,接着退还是 a

练习

模式串 t=‘abcaabbcabcaabdab’ ,该模式串的 next 数组的值为( D ) , nextval 数组的值为 ( F

A 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2

B 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2

C 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1

D 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2

E 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1

F 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1


(三)总结

BF(Brute Force)和KMP(Knuth-Morris-Pratt)算法是两种字符串匹配算法,它们的主要区别在于匹配过程中的策略和效率

  1. BF算法:
  • BF算法是一种简单直接的字符串匹配算法,也被称为朴素算法。
  • 它的思想是从主串中的每个位置开始,逐个比较主串和模式串的字符,直到找到匹配或遍历完所有可能位置。
  • 当字符不匹配时,BF算法通过移动主串指针,重新从下一个位置开始匹配。
  • BF算法的时间复杂度为O(m*n),其中m为主串长度,n为模式串长度,最坏情况下需要遍历所有可能的匹配位置。
  • 由于BF算法每次只移动一位,对于大规模文本匹配效率较低。
  1. KMP算法:
  • KMP算法是一种高效的字符串匹配算法,通过利用已知信息减少不必要的字符比较次数。
  • 它利用模式串自身的特性,在匹配过程中跳过一部分已经匹配的字符,从而提高匹配效率。
  • KMP算法包括两个主要步骤:构建最长公共前后缀数组(next数组)和匹配过程。
  • 最长公共前后缀数组(next数组)记录了模式串中对于每个位置,匹配失败时应该跳过的字符数。
  • 在匹配过程中,当字符不匹配时,KMP算法通过查询next数组获取跳跃位置,而不是重新从头开始比较。
  • KMP算法的时间复杂度为O(m+n),其中m为主串长度,n为模式串长度,通过next数组的优化,可以在匹配过程中跳过一定数量的比较,从而提高效率。

以下是关于上述两种算法的小结:

  1. 总结起来,BF算法是一种简单直接的字符串匹配算法,逐个比较字符并逐位移动,效率较低;
  2. 而KMP算法是一种高效的字符串匹配算法,通过构建最长公共前后缀数组和跳跃匹配位置,减少不必要的字符比较次数,提高匹配效率。
  3. 因此,在大规模文本匹配的应用中,KMP算法通常比BF算法更加高效。
相关文章
|
7天前
|
算法 搜索推荐 程序员
第六十五练 字符串匹配 - Rabin-Karp算法
第六十五练 字符串匹配 - Rabin-Karp算法
10 1
|
7天前
|
算法 搜索推荐 程序员
第六十四练 字符串匹配 - Boyer-Moore算法
第六十四练 字符串匹配 - Boyer-Moore算法
10 0
|
7天前
|
算法 搜索推荐 程序员
第六十三练 字符串匹配 - KMP算法
第六十三练 字符串匹配 - KMP算法
10 2
|
7天前
|
算法 C语言 人工智能
|
7天前
|
算法
代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
26 1
|
7天前
|
算法
优选算法|【双指针】|611.有效三角形的个数
优选算法|【双指针】|611.有效三角形的个数
|
7天前
|
算法
优选算法|【双指针】|202.快乐数
优选算法|【双指针】|202.快乐数
|
7天前
|
算法
优选算法|【双指针】283.移动零
优选算法|【双指针】283.移动零
|
7天前
|
算法
优选算法|【双指针】|1089.复写零
优选算法|【双指针】|1089.复写零
|
7天前
|
机器学习/深度学习 算法
【优选算法专栏】专题四:前缀和(二)
【优选算法专栏】专题四:前缀和(二)
23 1