// 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++实现Bad Character Rule(坏字符规则)和Good Suffix Rule(好后缀规则)来优化Boyer-Moore(BM)字符串匹配算法。BM算法以其高效的性能在文本搜索、数据挖掘等多个领域广泛应用。 ...
**BM(Boyer-Moore)算法**是一种高效的串匹配算法,它通过预先计算模式串的偏移表来减少不必要的比较次数,从而提高了匹配效率。 ##### 1. BM算法原理 - **偏移表构建**:利用`dist`函数根据模式串`T`构建偏移表,...
下面将详细介绍几种常见的串匹配算法以及它们在C++中的实现。 1. **Brute Force (BF) 算法**:也称为朴素匹配算法,是最简单的串匹配方法。它从主串的每个位置开始,逐个比较模式串和主串的字符,如果发现不匹配则...
以上是两种不同的串匹配算法在C++中的实现。BF算法简单直观但效率较低;而BM算法虽然实现相对复杂,但由于采用了更有效的搜索策略,因此在大多数情况下能够提供更快的匹配速度。在实际应用中,选择哪种算法取决于...
**BM(Boyer-Moore)算法** BM算法,全称为Boyer-Moore字符串查找算法,是由Robert S. Boyer和J Strother Moore在1977年...通过C++的实现,我们可以将其整合到各种应用程序中,进行文本分析、搜索或者模式匹配等任务。
为了实现这些功能,开发者应用了两种经典的字符串匹配算法——KMP算法和BM算法。 KMP(Knuth-Morris-Pratt)算法是一种高效的字符串搜索算法,其核心思想是避免在模式匹配过程中进行不必要的字符比较。通过预处理...
对于更复杂的单词查找问题,可能会用到模式匹配算法,如KMP算法(Knuth-Morris-Pratt算法)、BM算法(Boyer-Moore算法)等。而对于大型文本或数据库中的单词查找,则可能涉及到索引技术。 #### 教学意义 对于学习...
- **优化匹配算法**:引入更高效的串匹配算法,如KMP算法或BM算法。 - **增强功能**:支持更灵活的匹配选项,如忽略大小写、使用通配符等。 - **代码安全**:避免使用已废弃的函数,改用更安全的替代方案,如`fgets...
常见的有基于词典的匹配算法(如BM算法、HMM隐马尔科夫模型)、统计模型(如CRF条件随机场、LSTM长短时记忆网络)等。在C++实现中,词典匹配是最基础的方法,它依赖于预构建的词典,通过查找和匹配待分词文本中的...
- **二分图匹配(HOPCROFT-CARP 的算法)**:更高效的二分图匹配算法。 - **二分图最佳匹配(KUHN MUNKRAS 算法 O(M*M*N))**:在二分图中寻找最小成本的最大匹配。 - **无向图最小割 O(N^3)**:寻找无向图中的最小...
5. 正则表达式查找:支持更复杂的模式匹配,如通配符、重复、选择等,常见的实现有DFA(确定有限状态自动机)和NFA(非确定有限状态自动机)。 三、C++实现文本查找 C++作为一门强大的系统级编程语言,提供了丰富...
- HOPCROFT-CARP算法是另一种高效的二分图匹配算法,通常比匈牙利算法更快。 - **二分图匹配(KUHNMUNKRAS算法O(M*M*N))** - KUHNMUNKRAS算法是另一种解决二分图匹配问题的算法,其时间复杂度为O(M^2 * N)。 - ...