串的存盤結構

#define MAXLEN 255
typedef struct
{
	char ch[MAXLEN+1];
	int length;
}SString;

結構由一個字符陣列和代表長度的length組成

一、BF演算法

目的：從S中匹配子串T，并回傳第一個匹配字符的位置
實作：這是最簡單直觀的模式匹配演算法
①從兩個串逐個字符相匹配，如果相同繼續匹配，不同則S串指標退回到上一次匹配的下一位，T串指標退回到首位，繼續匹配，
②最后當j>T.length則說明匹配成功，回傳當前S串的i-T.length即為第一個匹配字符的位置

int Index_BF(SString S,SString T,int pos)
{
	int i=pos,j=1;
	while (i<=S.length&&j<=T.length)
	{
		if(S.ch[i]==T.ch[j]) {++i;++j;}
		else {i=i-j+2;j=1;}
	}
	if(j>T.length) return i-T.length;
	else return 0;
}

若S串為“abcababca”,T串為“abcabx”

當T串末位‘x’與主串’a’不匹配時，T串整體向后移動繼續匹配

當T串末位‘x’與主串’b’不匹配時，T串整體向后移動繼續匹配
直到匹配完成為止，此樣例無法匹配完成，

二、KMP模式匹配演算法

目的：從S中匹配子串T，并回傳第一個匹配字符的位置
實作：這是提高效率的模式匹配演算法
①從兩個串逐個字符相匹配，如果相同繼續匹配，不同則S串指標i不回溯，將next[j]=j將當前位置的next陣列值賦給j，繼續匹配，
②最后當j>T.length則說明匹配成功，回傳當前S串的i-T.length即為第一個匹配字符的位置

int Index_KMP(SString S,SString T,int pos)
{
	int i=pos,j=1;
	int next[MAXLEN];
	get_next(T,next);
	while (i<=S.length&&j<=T.length)
	{
		if(j==0||S.ch[i]==T.ch[j]){++i;++j;}
		else j=next[j];
	}
	if(j>T.length) return i-T.length;
	else return 0;
}

若S串為“abcababca”,T串為“abcabx”

如圖，當T串末位‘x’與主串’a’不匹配時
觀察T串第一個字符’a’與第二三個字符bc不同，而S串第二三個字符與T串二三個字符相匹配，所以直接跳過T串首字符’a’與S串第二三個字符的比較

因為T串前兩個字符ab和T串第四五個字符ab相同，而第四五個字符已經與S串第四五個字符相比較匹配，所以也可以跳過

此時j=3，直接從T串第三個字符開始比較，
KMP演算法避免了BF演算法中多余的“回溯”，大大避免重復遍歷的情況

求next陣列的值

下面來看一看如何得到next陣列：
通過上面的例子可以看出，next陣列的值與S串無關，只與T串本身的結構有關，
我們把T串各個位置的j值的變化定義為一個陣列next，那么next的長度就是T串的長度，我們可以得到定義：

void get_next(SString T,int next[])
{
	int i=1,j=0;
	next[1]=0;
	while (i<T.length)
	{
		if(j==0||T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}
		else j=next[j];
	}
}

當j=1時next[1]=0
當j=2時next[2]=1
當j=3時next[3]=1
當j=4時，前三位前綴后綴都是‘a’,所以next[4]=2
當j=5時，前四位前綴后綴都是‘ab’,next[5]=3
當j=6時，前五位前綴后綴都是‘aba’,next[6]=4
當j=7時，前六位前綴后綴都是‘a’,next[7]=2
當j=8時，前七位前綴后綴都是‘a’,next[8]=2
當j=9時，前八位前綴后綴都是‘ab’,next[9]=3

三、KMP模式匹配演算法改進

int Index_KMP(SString S,SString T,int pos)
{
	int i=pos,j=1;
	int next[MAXLEN];
	get_nextval(T,next);
	while (i<=S.length&&j<=T.length)
	{
		if(j==0||S.ch[i]==T.ch[j]){++i;++j;}
		else j=next[j];
	}
	if(j>T.length) return i-T.length;
	else return 0;
}

KMP演算法存在一定的缺陷
例如當S=‘aaaabcde’，T=‘aaaaax’時
T的next陣列值分別為012345，當匹配i=5、j=5時，發現b與a不相等，因此j=next[5]=4,仍然不等j=next[4]=3…以此類推直到j=next[1]=0,此時i++、j++，得到i=6、j=1,繼續向后匹配，
我們可以發現其中的步驟可以省略，T串中a與后四個字符均相等，我們可以用首位的next[1]的值取代后續字符next[j]的值，

求nextval陣列的值

void get_nextval(SString T,int nextval[])
{
	int i=1,j=0;
	nextval[1]=0;
	while (i<T.length)
	{
		if(j==0||T.ch[i]==T.ch[j])
		{
			++i;++j;
			if(T.ch[i]!=T.ch[j])nextval[i]=j;
			else nextval[i]=nextval[j];
		}
		else j=nextval[j];
	}
}

當j=1時next[1]=0，nextval[1]=0
當j=2時next[2]=1,第二位字符的next值為1,第一位為a,b與a不同，所以nextval[2]=next[2]=1
當j=3時next[3]=1,第三位的字符next值為1,第一位為a,相同，所以nextval[1]=nextval[1]=0
當j=4時next[4]=2,第四位的字符next值為2,第二位為b,相同，所以nextval[1]=nextval[2]=1
當j=5時next[5]=3,第五位的字符next值為3,第三位為a,相同，所以nextval[5]=nextval[3]=0
當j=6時next[6]=4,第六位的字符next值為4,第四位為b,a與b不同，所以nextval[6]=next[6]=4
當j=7時next[7]=2,第七位的字符next值為2,第二位為b,a與b不同，所以nextval[7]=next[7]=2
當j=8時next[8]=2,第八位的字符next值為2,第二位為b,相同，所以nextval[8]=nextval[2]=1
當j=9時next[9]=3,第九位的字符next值為3,第三位為a,相同，所以nextval[9]=nextval[3]=0

改進后的KMP演算法，是在計算出next值的同時，如果a位字符與它next值指向的b位字符相等，則該a位的nextval就和b位的nextval相等；
如果不等，則該a位的nextval值就是它自己的next的值，

總結

本篇介紹了串的結構和匹配模式演算法，并介紹了優化的KMP演算法

測驗代碼及運行實體

int main()
{
	SString cr,me;
	cr.length=10;
	for (int i = 1; i <= cr.length; i++)
	{
		cr.ch[i]=i+64;
		cout<<cr.ch[i];
	}
	cout<<endl;
	me.length=5;
	for (int i = 1; i <= me.length; i++)
	{
		me.ch[i]=i+69;
		cout<<me.ch[i];
	}
	cout<<endl;

	cout<<Index_BF(cr,me,1)<<endl;
	cout<<Index_BF(cr,me,1)<<endl;
	cout<<Index_KMP(cr,me,1);
	return 0;
}