【数据结构】BF算法匹配主串中是否包含子串

港控/mmm° 2023-02-16 06:44 25阅读 0赞

### BF算法匹配主串中是否包含子串 ###

*  算法思想：
 *  示意图
 *  代码实现

# 算法思想： #

*BF算法思想：  
将主串S中从pos位置开始和模式串T的第1个字符比较：  
若相等，则主串和模式指针i、j分别后移继续比较后续字符；  
若不相等，则主串指针回溯至本次开始比较位置的下一个位置(i=i-j+2)，  
模式串指针回溯至第1个字符(j=1)开始比较；  
直至S中的一个连续字符序列与T相等，则匹配成功，  
函数返回值为S中从pos位置起与T匹配的子序列的第1个字符在S中的位置；  
否则，匹配失败，返回值为0。*

# 示意图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70]

# 代码实现 #

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <cstring>
    
    using namespace std;
    #define OK  1
    #define OVERFLOW -1
    #define ERROR    0
    typedef int status;
    
    //串的堆式存储结构
    typedef struct {
        
        char *ch;
        int length;
    
    } HString;
    
    
    //字符串赋值操作  status StrAssign(HString &T, char* chars)------将输入的字符串赋值给主串或模式串
    status StrAssign(HString &T, char *chars) {
        
        int len = strlen(chars);//获取字符串的长度
        T.ch = (char *) malloc(len * sizeof(char));//动态分配空间
        T.length = len;
        for (int i = 0; i <len ; i++) {
        
            T.ch[i]=chars[i];
        }
    
    
    }
    
    //BF模式匹配算法  status Index(HString S, HString T, int pos)------从主串S的第pos位置开始查找模式串T
    status Index(HString S, HString T, int pos) {
        
        int j = 1,i=pos;
       while (i<S.length&& j<T.length){
        
            if (S.ch[i] == T.ch[j]) {
        
                ++i;
                ++j;
            } else {
        
                i = i - j + 2;
                j = 1;
            }
            if (j == T.length) {
        
                return i-T.length+1;
            }
    
        }
    }
    int main() {
        
        HString s, t;//s为主串，T为模式串
        int pos;//从主串的第几个位置查找
        int WZ;//模式串第一次在主串中出现的位置
        char str[100];
        s.ch = NULL;
        t.ch = NULL;
        cout << "请输入主串S，按回车结束输入！" << endl;
        cin.getline(str, 100);//如果是用cin方法输入，那么如果我输入的是' '，那么只会匹配‘ ’前面的字符串，用cin.getline使得遇见‘ ’也匹配
        StrAssign(s, str);//赋值操作
        cout <<s.ch<< "主串长度为：" << s.length << endl;
        cout << "请输入模式串T，按回车结束输入！" << endl;
        cin.getline(str, 100);
        StrAssign(t, str);//赋值操作
        cout << t.ch<<"模式串长度为：" << t.length << endl;
    
        if (t.length > s.length) {
        
            cout << "模式串的长度大于主串的长度，无法实施查找操作，程序结束！" << endl;
            return 1;
        }
    
        cout << "请输入要在主串中查找模式的起始位置: ";
        cin >> pos;
    
        WZ = Index(s, t, pos);
        if (WZ != 0) cout << "模式匹配成功，模式在主串中第一次出现的位置为:" << WZ << endl;
        else cout << "模式匹配失败，主串中没有查找到该模式" << endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609084102703.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609085017199.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70