algo4.cpp

实验中我们使用了四种方法进行串匹配

#include"algo4.h"
void kmpnext(char *par,int pmun,int *next)
{
	int j=-1;
	for(int i=0;i<pmun;i++)
	{
		next[i]=j;
		while((j>-1)&&(par[i]!=par[j]))
			j=next[j];
		j=j+1;
	}
}
/*-------------------------------------------------------------------------------------------*/
void kmp(char* test,char *par,int tmun,int pmun)
{
	int *next;
	int j=0;
	next=(int*)malloc(sizeof(int)*(pmun));
	kmpnext(par,pmun,next);
	for(int i=0;i<tmun;i++)
	{
		while((j>-1)&&(par[j]!=test[i]))
			j=next[j];
		if(j==pmun-1)
		{
			cout<<i-pmun+2<<" ";
			j=next[j];
			while((j>-1)&&(par[j]!=test[i]))
	 		    j=next[j];
		}
		j=j+1;
	}
	cout<<endl;
}
/*-------------------------------------------------------------------------------------------*/
int preSo(char *par,int pmun,unsigned int *S,int asize)
{
	unsigned int j,lim;
    int i;
    for (i=0;i<asize;++i)
	{
		S[i] = ~0;
	}
	for (lim=0,i=0,j=1;i<pmun;++i,j<<=1)
	{
		S[par[i]-97]&=~j;
		lim|=j;
	}
	lim=~(lim>>1);
	return (lim);
}
/*-------------------------------------------------------------------------------------------*/
void so(char *par,int pmun,char *test,int tmun,int asize)
{
	unsigned int lim, state;
    unsigned int *S;
    S=(unsigned int *)malloc(sizeof(unsigned int)*asize);
    int j;
    lim=preSo(par,pmun,S,asize);
    for(state=~0,j=0;j<tmun;++j)
	{
		state=(state<<1)|S[test[j]-97];
        if (state<lim)
			cout<<j-pmun+2<<" ";
	}
	cout<<endl;
}
/*-------------------------------------------------------------------------------------------*/
void PreBc(char *par,int pmun,int *Bc,int asize)
{
	for(int i=0;i<asize;i++)
		Bc[i]=pmun;
	for(i=0;i<pmun-1;i++)
		Bc[par[i]-97]=pmun-i-1;
}
/*-------------------------------------------------------------------------------------------*/
int memcmp(char *par,char *test,int j,int pmun)
{
	int i=0;
	while((par[i]==test[j+i])&&(i<pmun))i++;
	if(i==pmun)return(0);
	else return(1);
}
/*-------------------------------------------------------------------------------------------*/
void horspool(char *par,int pmun,char *test, int tmun,int asize) 
{
	int j, *Bc;
    Bc=(int *)malloc(sizeof(int)*asize);
    char c;
    PreBc(par,pmun,Bc,asize); 
    j=0;
    while(j<tmun-pmun+1)
	{
		c=test[j+pmun-1];
        if(par[pmun-1]==c&&memcmp(par,test,j,pmun)==0)
			cout<<j+1<<" ";
		j+=Bc[c-97];
	}
	cout<<endl;
}
/*-------------------------------------------------------------------------------------------*/
void QBc(char *par,int pmun,int *QB,int asize)
{
	for(int i=0;i<asize;i++)
		QB[i]=pmun+1;
	for(i=0;i<pmun;i++)
		QB[par[i]-97]=pmun-i;
}
/*-------------------------------------------------------------------------------------------*/
void QS(char *par,int pmun,char *test, int tmun,int asize)
{
	int j, *QB;
    QB=(int *)malloc(sizeof(int)*asize);
    QBc(par,pmun,QB,asize); 
    j=0;
    while(j<tmun-pmun)
	{
		if(memcmp(par,test,j,pmun)==0) 
			cout<<j+1<<" ";
		j=j+QB[test[j+pmun]-97];
	}
	cout<<endl;
}
/*-------------------------------------------------------------------------------------------*/