string_match.cpp

串匹配算法,KMP,QS,Horspool,RP

# include <iostream>
# include <math.h>
# include <time.h>
# include <fstream>
# include <string>
# include <windows.h>

using namespace std;

# define none -1          //若在文本串中找不到匹配则返回none

void Init_Tstring (char * T, int n, char * ifile)
{
	//初始化文本串
	srand ((unsigned)time(NULL));
	ofstream file;
	file.open(ifile,ios::app);

	file<<"文本串T的长度n为: "<<n<<endl;
	file<<"文本串的内容为: "<<endl;
	for (int i=1; i<=n; i++)
	{
		T[i] = rand()%94+33;   //字符为ASCII的33到126,为克打印字符，不包括空格
		file<<T[i];
	}
	file<<endl;
	file.close();
}

void Init_Pstring (char * P, int m, char * T, int n, char * ifile)
{
	//初始化模式串
	srand ((unsigned)time(NULL));
	ofstream file;
	file.open(ifile,ios::app);

	file<<"模式串P的长度m为: "<<m<<endl;
	file<<"模式串的内容为: "<<endl;

	int u = rand()%(n-m+1);       //模式串是在文本串中随机截取的
	for (int i=1; i<=m; i++)
	{
		P[i] = T[u+i];
		file<<P[i];
	}
	file<<endl;
	file.close();
}

void PNext (char * P, int * Next, int m)
{
	int j = 0;
	for (int i=1; i<=m; i++)
	{
		Next[i] = j;
		while (j>0 && P[i]!=P[j])
			j = Next[j];
		j = j+1;
	}
}

int KMP (char * P, int m, char * T, int n)
{
	int * Next = new int[m+1];
	PNext (P, Next, m);
	int j = 1;
	for (int i=1; i<=n; i++)
	{
		while (j>0 && T[i]!=P[j])
			j = Next[j];
		if (j==m)
			return (i-m+1);
		j = j+1;
	}
	return none;
}

int KP (char * P, int m, char * T, int n)
{
	int d = 1;
	int Phash = 0;
	int Thash = 0;
	for (int i=1; i<=m-1; i++)
		d = d<<1;
	for (i=1; i<=m; i++)
	{
		Phash = (Phash<<1)+P[i];
		Thash = (Thash<<1)+T[i];
	}
	int j = 1;
	while (j<=n-m+1)
	{
		if (Phash == Thash)
		{
			i = 1;
			while (P[i]==T[j-1+i] && i<=m)
				i++;
			if (i>m)
				return j;
		}
		Thash = ((Thash-T[j]*d)<<1)+T[j+m];
		j++;
	}
	return none;
}

void Pre_QsBc (char * P, int m, int Qs_Bc[])
{
	for (int i=1; i<137; i++)
		Qs_Bc[i] = m+1;
	for (i=1; i<=m; i++)
		Qs_Bc[P[i]] = m+1-i;
}

int QS (char * P, int m, char * T, int n)
{
	int Qs_Bc[137];
	Pre_QsBc (P, m, Qs_Bc);

	int j = 1;
	while (j<=n-m+1)
	{
		int i = 1;
		while (P[i]==T[j-1+i] && i<=m)
			i++;
		if (i>m)
			return j;
		j = j+Qs_Bc[T[j+m]];
	}

	return none;
}

void Pre_HoBc (char * P, int m, int Ho_Bc[])
{
	for (int i=1; i<137; i++)
		Ho_Bc[i] = m;
	for (i=1; i<=m-1; i++)
		Ho_Bc[P[i]] = m-i;
}

int HORSPOOL (char * P, int m, char * T, int n)
{
	int Ho_Bc[137];
	Pre_HoBc (P, m, Ho_Bc);
	int i = m;
	while (i<=n)
	{
		int k = 1;
		while (k<=m && P[m-k+1]==T[i-k+1])
			k = k+1;
		if (k>m)
			return (i-m+1);
		else
			i = i+Ho_Bc[T[i]];
	}
	return none;
}

void Timing (char * P, int m, char * T, int n, char * ifile)
{
	LARGE_INTEGER litmp;
	LONGLONG QPart1, QPart2;
	double dfMinus, dfFreq, dfTim;
	QueryPerformanceFrequency (& litmp);        // 获得计数器的时钟频率
	dfFreq = (double)litmp.QuadPart;

	ofstream file;
	file.open(ifile,ios::app);

	file<<endl;

	QueryPerformanceCounter (& litmp);          // 获得初始值  
	QPart1 = litmp.QuadPart;

	int i = KMP (P, m, T, n);

	QueryPerformanceCounter (& litmp);          // 获得终止值 
	QPart2 = litmp.QuadPart;
	dfMinus = (double)(QPart2-QPart1);
	dfTim = dfMinus / dfFreq;                   // 获得所用的时间
	if (i==none)
		file<<"在文本串中找不到匹配串"<<endl;
	else
	    file<<"KMP算法找到的匹配串在文本串中的起始位置为: "<<i<<endl;
    file<<"KMP算法程序的运行时间为:  "<<dfTim<<" 秒"<<endl;

    QueryPerformanceCounter (& litmp);          // 获得初始值  
	QPart1 = litmp.QuadPart;

	i = KP (P, m, T, n);

	QueryPerformanceCounter (& litmp);          // 获得终止值 
	QPart2 = litmp.QuadPart;
	dfMinus = (double)(QPart2-QPart1);
	dfTim = dfMinus / dfFreq;                   // 获得所用的时间
	if (i==none)
		file<<"在文本串中找不到匹配串"<<endl;
	else
	    file<<"KP算法找到的匹配串在文本串中的起始位置为: "<<i<<endl;
    file<<"KP算法程序的运行时间为:  "<<dfTim<<" 秒"<<endl;

	QueryPerformanceCounter (& litmp);          // 获得初始值  
	QPart1 = litmp.QuadPart;

	i = QS (P, m, T, n);

	QueryPerformanceCounter (& litmp);          // 获得终止值 
	QPart2 = litmp.QuadPart;
	dfMinus = (double)(QPart2-QPart1);
	dfTim = dfMinus / dfFreq;                   // 获得所用的时间
	if (i==none)
		file<<"在文本串中找不到匹配串"<<endl;
	else
	    file<<"QS算法找到的匹配串在文本串中的起始位置为: "<<i<<endl;
    file<<"QS算法程序的运行时间为:  "<<dfTim<<" 秒"<<endl;

	QueryPerformanceCounter (& litmp);          // 获得初始值  
	QPart1 = litmp.QuadPart;

	i = HORSPOOL (P, m, T, n);

	QueryPerformanceCounter (& litmp);          // 获得终止值 
	QPart2 = litmp.QuadPart;
	dfMinus = (double)(QPart2-QPart1);
	dfTim = dfMinus / dfFreq;                   // 获得所用的时间
	if (i==none)
		file<<"在文本串中找不到匹配串"<<endl;
	else
		file<<"HORSPOOL算法找到的匹配串在文本串中的起始位置为: "<<i<<endl;
    file<<"HORSPOOL算法程序的运行时间为:  "<<dfTim<<" 秒"<<endl;

	file<<endl;
	file.close();
}

int main (void)
{
	ofstream ofile;
	ofile.open("output.txt");
	ofile.close();

	for (int i=4; i<=14; i=i+2)
	{
		ofstream file;
	    file.open("output.txt", ios::app);

		int n = (int)pow(2, i);  //文本串长度
		char * T = new char[n+1];
		Init_Tstring (T, n, "output.txt");
		file<<endl;

		int m = i;
		char * P = new char[m+1];
		Init_Pstring (P, m, T, n, "output.txt");
		Timing (P, m, T, n, "output.txt");
		delete [] P;

		m = 2*i;
		P = new char[m+1];
		Init_Pstring (P, m, T, n, "output.txt");
		Timing (P, m, T, n, "output.txt");
		delete [] P;

		m = n/4;
		P = new char[m+1];
		Init_Pstring (P, m, T, n, "output.txt");
		Timing (P, m, T, n, "output.txt");
		delete [] P;

		delete [] T;
		file<<"---------------------------------------------------------"<<endl;
		file.close();
	}

	return 1;
}