horspool.cpp

来自「此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,」· C++ 代码 · 共 61 行

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

char P[]={"BARBER"};//模式串存放在数组P中
char T[]={"JIM_SAW_ME_IN_A_BARBERSHOP"};//文本串存放在数组T中
int Table[256];//存放填充移动表
int m,n; //m为模式串长度，n为文本串长度

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

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

int Horspool(){
	ShiftTable();//生成移动表
	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 i=i+Table[T[i]]; //修改i的值，以进行下一轮的比较
	}
	return -1; //没有找到匹配的串
}

void main(){
	int i;
	printf("Horspool算法实现模式匹配:\n");
	printf("文本串:JIM_SAW_ME_IN_A_BARBERSHOP\n模式串:BARBER\n");
	int j;
	for(j=0;P[j]!='\0';j++)
		m=j+1; //m为模式串的长度
//	printf("m=%d",m);
	
	for(j=0;T[j]!='\0';j++)
		n=j+1; //n为文本串的长度
//	printf("n=%d",n);

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

	system("PAUSE");
}