BM模式匹配算法I C++实现

落日映苍穹つ 2022-05-15 13:24 138阅读 0赞

**// 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  
请按任意键继续. . .**