[数据结构] BF 算法和 KMP 算法 - BF 算法
最编程
2024-07-19 16:36:02
...
#include<iostream>
using namespace std;
//#include <string.h>//字符串处理
#define MAXSIZE 255
//串的定长顺序存储结构
typedef struct {
char ch[MAXSIZE+1];
int length;
} SString;
//bf算法
int IndexBF(SString S,SString T) {
//从主串和模式串的第一个开始比较,因为第一个字符下标是0,所以i=0,j=0
int i=0;
int j=0;
int count = 0;
//当所有字符比较完后就跳出循环 下标从0开始,对应长度就减一
while(i<=S.length-1 && j<=T.length-1) {
if(S.ch[i]==T.ch[j]) {
++i; //匹配上就都比较下一个字符
++j;
count++;
} else {
i = i-j+1; //匹配不上,i移动到下一个字符,j从头开始
j=0;
}
}
//当模式串的j>T.length-1,说明模式串的所有字符都匹配到主串中的一个连续字符序列,
// 匹配成功,返回匹配上的第一字符在主串中的位置
if(j>T.length-1) return count; //其实是i-(T.length-1) 得到匹配上的第一字符在主串中的位置
else return 0;
}
//主函数
int main() {
//输入主串和模式串
SString S,T;
cout<<"输入主串和主串长度(中间用空格隔开)"<<endl;
cin >>S.ch>>S.length;
cout<<"输入模式串和模式串的长度(中间用空格隔开)"<<endl;
cin >>T.ch>>T.length;
//调用bf算法
cout<<"恭喜你,在主串的第"<<IndexBF(S,T)<<"个字符开始匹配上了"<<endl;
}
推荐阅读
-
数据结构与算法--排序算法:堆排序 最大堆(大顶堆)和 最小堆(小顶堆)详解
-
探索二叉树、红黑树、递归树、堆和堆排序的数据结构与算法(第四部分),以及堆的实际应用
-
数组和特殊矩阵压缩存储详解(第25讲) - 408数据结构与算法实践解析
-
掌握核心:408数据结构系列学习笔记——探索字符串、简单模式匹配与KMP算法及其升级版
-
利用BF算法进行病毒检测的方法探析
-
[数据结构] BF 算法和 KMP 算法 - BF 算法
-
python cookbook 内容提炼 - 第 1 章 数据结构和算法
-
数据结构和算法(0-1)----递归
-
数据结构 - 算法的时间复杂性和空间复杂性 - 3. 空间复杂性
-
MySQL Btree索引背后的数据结构和算法原理