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

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

算法思想:

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

示意图

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

代码实现

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

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

上一篇:ndn挖坑记(完)


下一篇:Wireshark过滤器详解