串的模式匹配-BF算法

妖狐艹你老母 2022-09-28 13:09 199阅读 0赞

串的模式匹配经常需要用到，判断一个字符串是否是另外一个字符串的一部分。前者称为子串或模式，后者成为主串或正文串。

先用最简单的BF算法实现串的模式匹配。

算法思路：先从主串和子串第一个位置开始进行比较。如果相等，那么继续比较后面的字符，否则从主串失配的下一个元素开始和子串的第一个元素继续匹配。直到比较到主串最后位置，如果一直不匹配，则匹配失败，否则得到匹配的位置。

最好情况时间复杂度：O(n+m)  
（假设每次不成功的匹配都发生在子串的第一个字符）  
最坏情况时间复杂度：O(n\*m)  
（假设每次不成功的匹配都发生在子串的最后一个字符）

算法优点：思路简单明了。  
算法缺点：时间复杂度高。

#include <iostream>
    using namespace std;
    
    #include<stdio.h>
    #include<string.h>
    
    //字符串采用数组存储.
    typedef struct
    {
        char ch[100];
        int length;
    }HString;
    
    //BF算法
    int bf(HString *s,HString *t)//如果匹配成功，返回匹配位置。匹配失败，返回0
    {
       int i=1;
       int j=1;
       //位置从第一位开始算起
       while(i<=s->length&&j<=t->length)
       {
           if(s->ch[i]==t->ch[j])//如果匹配成功，都往后找元素继续比较
           {
               i++;
               j++;
           }
           else//匹配失败
           {
               i=i-j+2;//可画图分析得到i需要返回的位置
               j=1;//i回到起点
           }
       }
       if(j>t->length)
         return i-(t->length);
       else
         return 0;
    }
    int main()
    {
    
        HString s,t;
        int i;
        int j;
        scanf("%s",s.ch);
        //gets(t);
        scanf("%s",t.ch);
        s.length=strlen(s.ch);
        t.length=strlen(t.ch);
        //将字符串后移一位，从1号位置开始处理
        for(i=s.length-1;i>=0;i--)
        {
            s.ch[i+1]=s.ch[i];
        }
        for(j=t.length;j>=0;j--)
        {
            t.ch[j+1]=t.ch[j];
        }
        if(bf(&s,&t)==0)
            printf("对不起，你输入的两个字符串不匹配！\n");
        else
            printf("匹配的位置为：%d\n",bf(&s,&t));
        return 0;
    
    }

CB下调试成功  
![这里写图片描述][SouthEast]

匹配失败后主串新开始匹配的初始位置（有点丑勉强看看）

![这里写图片描述][SouthEast 1]

总结：BF算法非常简单。我在实现时遇到的困难是字符串的数据结构的选择和操作。对指针的理解还有欠缺，只有多使用才能用好指针吧。KMP算法后续会实现，这个才是常用的。

[SouthEast]: /images/20220708/e4dfb84c640046ccb1640b26c203ed59.png
[SouthEast 1]: /images/20220708/dce5f3c5989441969105ad27baa62a4c.png