C++程式設計練習(7)----“KMP模式比對算法“字元串比對

子串在主串中的定位操作通常稱做串的模式比對。

KMP模式比對算法實作：

/* Index_KMP.h頭檔案 */
#include<string>
#include<sstream>

void get_next(std::string T,int *next)
{
	unsigned int i,j;
	i=1;
	j=0;
	next[1]=0;
	while(i<(T.size()-1))	/* 此處T的首個字元T[0]表示串T的長度，不參與計算 */
	{
		if(j==0||T[i]==T[j])	/* T[i]表示字尾的單個字元，T[j]表示字首的單個字元 */
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];		/* 若字元不相同，則j值回溯 */
	}
}

int Index_KMP(std::string S, std::string T, unsigned int pos)
{
	std::string s,t;				/*在字元串S,T的最前插入一個字元來儲存串的長度值，*/
	std::ostringstream s1,s2;		/*用來保證字元串的有用元素是從下标1開始*/
	s1<<S.size()<<S;				/*将新的數組儲存為s，t*/
	s2<<T.size()<<T;
	s=s1.str();
	t=s2.str();
	unsigned int i=pos;	/* i用于主串s目前位置下标值，若pos不為1，則從pos位置開始比對 */
	unsigned int j=1;	/* j用于字串t中目前位置下标值 */
	int next[255];	/* 定義一next數組 */
	get_next(t,next);	/* 對串t作分析，得到next數組 */
	while (i<=(s.size()-1) && j<=(t.size()-1))	/* 若i小于S的長度且j小于T的長度時，循環繼續 */
	{
		if ( j==0 || s[i]==t[j])	/* 兩字母相等則繼續，相對于樸素算法增加了j=0判斷 */
		{
			++i;
			++j;
		}
		else		/* 指針後退重新開始比對 */
		{
			j=next[j];		/* j退回合适的位置，i值不變 */
		}
	}
	if ( j>(t.size()-1) )
		return i-(t.size()-1);
	else
		return 0;
}
           

KMP模式比對算法的改進：

/* Index_KMP.h頭檔案 */
#include<string>
#include<sstream>

void get_nextval(std::string T,int *nextval)
{
	unsigned int i,j;
	i=1;
	j=0;
	nextval[1]=0;
	while(i<(T.size()-1))	/* 此處T的首個字元T[0]表示串T的長度，不參與計算 */
	{
		if(j==0||T[i]==T[j])	/* T[i]表示字尾的單個字元，T[j]表示字首的單個字元 */
		{
			++i;
			++j;
			if (T[i]!=T[j])			/*若目前字元與字首字元不同*/
				nextval[i]=j;		/*則目前的j為nextval在i位置的值*/
			else
				nextval[i]=nextval[j];	/*如果與字首字元相同，則将字首字元的nextval值指派給nextval在i位置的值*/
			
		}
		else
			j=nextval[j];		/* 若字元不相同，則j值回溯 */
	}
}

int Index_KMP(std::string S, std::string T, unsigned int pos)
{
	std::string s,t;				/*在字元串S,T的最前插入一個字元來儲存串的長度值，*/
	std::ostringstream s1,s2;		/*用來保證字元串的有用元素是從下标1開始*/
	s1<<S.size()<<S;				/*将新的數組儲存為s，t*/
	s2<<T.size()<<T;
	s=s1.str();
	t=s2.str();
	unsigned int i=pos;	/* i用于主串s目前位置下标值，若pos不為1，則從pos位置開始比對 */
	unsigned int j=1;	/* j用于字串t中目前位置下标值 */
	int next[255];	/* 定義一next數組 */
	get_nextval(t,next);
	while (i<=(s.size()-1) && j<=(t.size()-1))	/* 若i小于S的長度且j小于T的長度時，循環繼續 */
	{
		if ( j==0 || s[i]==t[j])	/* 兩字母相等則繼續，相對于樸素算法增加了j=0判斷 */
		{
			++i;
			++j;
		}
		else		/* 指針後退重新開始比對 */
		{
			j=next[j];		/* j退回合适的位置，i值不變 */
		}
	}
	if ( j>(t.size()-1) )
		return i-(t.size()-1);
	else
		return 0;
}
           

比對算法不做變化，隻需要将"get_next(T,next)"改為“get_nextval (T,next)”即可。

總結：改進過的KMP算法，它是在計算出 next 值的同時，如果a位字元與它 next 值指向的 b 位字元相等，則該 a 位的nextval 就指向 b 位的 nextval 值，如果不等，則該 a 位的 nextval 值就是它自己 a 位的 nextval 的值。