#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個文件信息