boyer_moore.cpp

此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,并实现了平衡二叉树中的结点删除 Boyer_Moore算法的串模式匹配 Horspool算法的串模式匹配 Grap

//Boyer_Moore算法实现模式匹配
#include <stdio.h>
#include <stdlib.h>

char P[]={"BAOBAB"}; //模式串存放在数组P中
char T[]={"BESS_KNEW_ABOUT_BAOBABS"}; //文本串存放在数组T中

int BadTable[256]; //存放坏符号移动表
int GoodPostTable[5]={2,5,5,5,5};//存放好后缀移动表
int m,n; //m为模式串长度，n为文本串长度

void CreateBadTable(){//生成坏符号移动表的函数
	int j;
	for(j=0;j<n;j++)
		BadTable[T[j]]=m; //移动表中元素初始值设为模式串长度m

	for(j=0;j<m-1;j++) //修改移动表Table中含模式串元素的值
		BadTable[P[j]]=m-1-j;
}


int Boyer_Moore(){
	CreateBadTable();//生成移动表
	int d1,d2,d; //d1=max{t1(c)-k,1}
	
	int k;       //令k为匹配字符的个数
	int i=m-1;   //令i指向模式最右端的位置
	while(i<=n-1){
		k=0;  //匹配字符个数初始值为0
		while((k<=m-1)&&(P[m-1-k]==T[i-k]))//当元素匹配时，匹配个数k增加
			k++;
		if(k==m) //找到匹配的串
			return i-m+1;//返回匹配串的起始位置
		else {
			char c=T[i-k]; //c保存不匹配的字符
		//	printf("%c ",c);
			d1=(BadTable[c]-k)>1?(BadTable[c]-k):1; //d1=max{t1(c)-k,1}
			d2=GoodPostTable[k]; //d2为好后缀数组元素
			d=(d1>d2)?d1:d2;    //d为d1,d2中的较大值

			i=i+d; //修改i的值，以进行下一轮的比较
		}
	}
	return -1; //没有找到匹配的串
}

void main(){
	int i;
	printf("Boyer_Moore算法实现模式匹配:\n");
	printf("文本串:BESS_KNEW_ABOUT_BAOBABS\n模式串:BAOBAB\n");	

	int j;
	for(j=0;P[j]!='\0';j++)
		m=j+1; //m为模式串的长度
	
	for(j=0;T[j]!='\0';j++)
		n=j+1; //n为文本串的长度

	i=Boyer_Moore(); //Boyer_Moore算法实现模式匹配
	if(i!=-1)
		printf("找到匹配的子串，匹配的位置为：%d\n\n",i+1);
	else
		printf("没有找到匹配的子串!\n\n");

	system("PAUSE");
}