// BM模式匹配算法I.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 200
using namespace std;
void get_dist(int *dist,char *t,const int lenT)
{
int i;
for(i=0;i<=MAX;i++)
dist[i] = lenT;
for(i=0;i<lenT;i++)
dist[(int)t[i]] = lenT-i-1;
}
//
int BM(char *s,char *t,int *dist,const int lenS,const int lenT)
{
int i,j,k;
i = lenT-1;
while(i<lenS)
{
j = lenT-1;
k = i;
while(j>=0&&s[k]==t[j])
{
j--;
k--;
}
if(j<0)
return i+2-lenT;
else
i = i + dist[s[k]];
}
if(i>=lenS)
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
char s[MAX],t[MAX];
int dist[MAX];
cout<<"请输入案例的个数:";
cin>>cases;
while(cases--)
{
cout<<"请输入主串:"<<endl;
cin>>s;
int lenS = strlen(s);
while(1)
{
cout<<"请输入需要匹配的模式串(以0结束):"<<endl;
cin>>t;
if(!strcmp(t,"0"))
break;
int lenT = strlen(t);
get_dist(dist,t,lenT);
int pos = BM(s,t,dist,lenS,lenT);
if(pos==0)
cout<<"没有匹配项!"<<endl;
else
cout<<"匹配的开始位置为:"<<pos<<endl;
}
}
system("pause");
return 0;
}
----------------------------------------------------程序测试-------------------------------------------------------------
请输入案例的个数:1
请输入主串:
heyongluoyao8
请输入需要匹配的模式串(以0结束):
he
匹配的开始位置为:1
请输入需要匹配的模式串(以0结束):
yong
匹配的开始位置为:3
请输入需要匹配的模式串(以0结束):
luo
匹配的开始位置为:7
请输入需要匹配的模式串(以0结束):
luoyao
匹配的开始位置为:7
请输入需要匹配的模式串(以0结束):
lao
没有匹配项!
请输入需要匹配的模式串(以0结束):
0
请按任意键继续. . .
分享到:
相关推荐
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
详细介绍了BM字符串匹配的方法及效率问题.
BM算法被认为是亚线性串匹配算法,它在最坏情况下找到模式所有出现的时间复杂度为O(mn),在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。
IBM模式匹配算法,对中文分析,信息分拣感兴趣的都可以去看看。
单模式匹配算法 BM算法 很经典的单模式算法
三维块匹配(BM3D)算法: 它首先把图像分成一定大小的块,根据图像块之间的相似性,把具有相似结构的二维图像块组合在一起形成三维数组,然后用联合滤波的方法对这些三维数组进行处理,最后,通过逆变换,把处理后的...
Snort入侵检测使用的BM模式匹配算法,单独列出来了。
全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
C++实现串匹配的BF,BM算法 C++实现串匹配的BF,BM算法 C++实现串匹配的BF,BM算法
多模式匹配算法 AC_BM算法 算法很经典 欢迎下载
使用了BM匹配算法计算了左右图像的视差图,本次BM匹配算法是使用python3.7,通过调用opencv库函数实现
图像BM3D算法 C++
不知道是自己的搜索能力太差还是怎么的,在CSDN上多花了6分下载这些资源,这是我上传的不需要分的资源,enjoy it...
BM字符匹配算法是当今简单有效的匹配算法,特别适合搜索匹配应用,这是一个简单的示例代码。
BM算法可以实现更高效率的模式匹配。分析和实验说明,BM匹配算法对于那些字符集比较大,而模式串中出现的字符比较少的时候,工作效率最快。而且,考虑KMP匹配方式的优化,可以结合KMP匹配和BM匹配,进一步提高效率。
WM算法,多模式匹配算法 经典算法 比BM算法好,转帖的 WM多模匹配算法的分析 模式匹配算法匹配速度测试结果
基于C++-opencv实现立体匹配:BM、SGBM算法实例 讲述如何通过opencv实现两种经典立体匹配算法 对图像中的目标场景恢复深度图并进行三维重建 本例程适用于想了解经典立体匹配算法的学生和入门者
BM算法 c语言实现 详细注解 高手作品
一种改进的串的模式匹配算法的探讨,穆维友,吴泽平,串的模式匹配算法一直都是计算机科学领域的研究焦点之一。本文首先分析了BF、KMP、BM三种算法,并提出了一种改进的Sundaynew算法,给��
在分析了目前常用的模式匹配算法的基础上,提出了一种改进的BM算法。实验结果表明改进的模式匹配算法能减少比较次数,有效地提高了匹配速度。