模式匹配—BF算法和KMP算法

模式匹配—从BF算法优化到KMP算法，含有详细注释，对应的讲述该算法的博文地址：http://blog.csdn.net/ns_code/article/details/19286279

#include
#include
using namespace std;
int kmp_index（const string &const string &int）;
void get_next（const string &int *int）;
void get_nextval（const string &int *int）;

int main（）
{
	char ch;
	do{
		string TagPtn;  
		int pos;
		cout<<“输入主串：“;
		cin>>Tag;
		cout<<“输入子串：“;
		cin>>Ptn;
		cout<<“输入主串中开始进行匹配的位置（首字符位置为0）：“;
		cin>>pos;
	
		int result = kmp_index（TagPtnpos）;
		if（result != -1）
			cout<<“主串与子串在主串的第“<		else
			cout<<“无匹配子串“<
		cout<<“是否继续测试（输入y或Y继续，任意其他键结束）：“;
		cin>>ch;
	}while（ch == ‘y‘ || ch == ‘Y‘）;
	return 0;
}

/*
返回子串Ptn在主串Tag的第pos个字符后（含第pos个位置）第一次出现的位置，若不存在，则返回-1
采用KMP算法，这里的位置全部以从0开始计算为准，其中T非空，0<=pos<=Tlen
*/
int kmp_index（const string &Tagconst string &Ptnint pos）
{
	int i = pos;  //主串当前正待比较的位置，初始为pos
	int j = 0;   //子串当前正待比较的位置，初始为0
	int Tlen = Tag.size（）;  //主串长度
	int Plen = Ptn.size（）;  //子串长度

	//求next数组的值，并逐个输出
	int *next = （int *）malloc（Plen*sizeof（int））;
	get_next（PtnnextPlen）;
//	get_nextval（PtnnextPln）;
	int t;
	cout<<“子串的next数组中的各元素为：“;
	for（t=0;t		cout<	cout<
	while（i	{
		if（j==-1 || Tag[i] == Ptn[j]）   
		{   //如果当前字符相同，或者在子串的第一个字符处失配，则继续向下比较
			i++;
			j++;
		}
		else   //如果当前字符不同，则i保持不变，j变为下一个开始比较的位置
		{   
			//next数组时KMP算法的关键，i不回退，
			//而是继续与子串中的nex[j]位置的字符进行比较
			j = next[j];
		}
	}

	if（j >= Plen）
		return i - Plen;
	else
		return -1;
}

/*
求next数组中各元素的值，保存在长为len的next数组中
*/
void get_next（const string &Ptnint *nextint len）
{
	int j = 0;
	int k = -1;
	next[0] = -1;

	while（j	{
		if（k == -1 || Ptn[j] == Ptn[k]）
		{   //如果满足上面分析的Pk = Pj的情况，则继续比较下一个字符，
			//并得next[j+1]=next[j]+1
			j++;
			k++;
			next[j] = k;
		}
		else
		{   //如果符合上面分析的第2种情况，则依据next[k]继续寻找下一个比较的位置
			k = next[k];
		}
	}
}


/*
求next数组的改进数组中各元素的值，保存在长为len的nextval数组中
*/
void get_nextval（const string &Ptnint *nextvalint len）
{
	int j = 0;
	int k = -1;
	nextval[0] = -1;

	while（j	{
		if（k == -1 || Ptn[j] == Ptn[k]）
		{   //如果满足上面分析的Pk = Pj的情况，则继续比较下一个字符，
			//并得next[j+1]=next[j]+1
			j++;
			k++;
			if（Ptn[j] != Ptn[k]）
				nextval[j] = k;
			else  //Ptn[j]与Ptn[k]相等时，直接跳到netval[k]
				nextval[j] = nextval[k];
		}
		else
		{   //如果符合上面分析的第2种情况，则依据next[k]继续寻找下一个比较的位置
			k = nextval[k];
		}
	}
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-02-19 16:55  模式匹配 BF—KMP\
     目录           0  2014-02-19 16:55  模式匹配 BF—KMP\KMP算法\
     目录           0  2014-02-19 16:55  模式匹配 BF—KMP\KMP算法\Debug\
     文件      548938  2014-02-19 14:35  模式匹配 BF—KMP\KMP算法\Debug\kmp_index.exe
     文件      787312  2014-02-19 14:35  模式匹配 BF—KMP\KMP算法\Debug\kmp_index.ilk
     文件      257871  2014-02-19 14:43  模式匹配 BF—KMP\KMP算法\Debug\kmp_index.obj
     文件     2056700  2014-02-18 00:04  模式匹配 BF—KMP\KMP算法\Debug\kmp_index.pch
     文件     1098752  2014-02-19 14:35  模式匹配 BF—KMP\KMP算法\Debug\kmp_index.pdb
     文件       74752  2014-02-19 14:43  模式匹配 BF—KMP\KMP算法\Debug\vc60.idb
     文件      110592  2014-02-19 14:43  模式匹配 BF—KMP\KMP算法\Debug\vc60.pdb
     文件        2857  2014-02-19 15:07  模式匹配 BF—KMP\KMP算法\kmp_index.cpp
     文件        3437  2014-02-17 11:05  模式匹配 BF—KMP\KMP算法\kmp_index.dsp
     文件         526  2014-02-17 11:05  模式匹配 BF—KMP\KMP算法\kmp_index.dsw
     文件       41984  2014-02-19 16:54  模式匹配 BF—KMP\KMP算法\kmp_index.ncb
     文件       48640  2014-02-19 16:54  模式匹配 BF—KMP\KMP算法\kmp_index.opt
     文件         680  2014-02-19 14:43  模式匹配 BF—KMP\KMP算法\kmp_index.plg
     目录           0  2014-02-19 16:55  模式匹配 BF—KMP\简单模式匹配算法—BF算法\
     目录           0  2014-02-19 16:55  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\
     文件      548950  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\simple_index.exe
     文件      786700  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\simple_index.ilk
     文件      255459  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\simple_index.obj
     文件     2056316  2014-02-16 20:04  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\simple_index.pch
     文件     1090560  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\simple_index.pdb
     文件       74752  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\vc60.idb
     文件      110592  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\Debug\vc60.pdb
     文件        1480  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\simple_index.cpp
     文件        3473  2014-02-16 16:49  模式匹配 BF—KMP\简单模式匹配算法—BF算法\simple_index.dsp
     文件         532  2014-02-16 17:04  模式匹配 BF—KMP\简单模式匹配算法—BF算法\simple_index.dsw
     文件       41984  2014-02-17 15:09  模式匹配 BF—KMP\简单模式匹配算法—BF算法\simple_index.ncb
     文件       48640  2014-02-17 15:09  模式匹配 BF—KMP\简单模式匹配算法—BF算法\simple_index.opt
     文件        1196  2014-02-17 15:08  模式匹配 BF—KMP\简单模式匹配算法—BF算法\simple_index.plg
............此处省略0个文件信息