4.3.1 求子串位置的定位函數(shù)Index(S,T,pos)

子串的定位操作通常稱做串的模式匹配（其中T稱為模式串），采用定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)，可以寫(xiě)出不依賴于其他串操作的匹配算法。

算法4.5：

下面是書(shū)中的偽代碼：

int Index(SString S, SString T, int pos) { 	// 返回子串T在主串S中第pos個(gè)字符之后的位置。	// 若不存在，則函數(shù)值為0。	// 其中，T非空，1≤pos≤StrLength(S)。	int i = pos;	int j = 1;	while (i <= S[0] && j <= T[0]) 	{		if (S[i] == T[j]) // 繼續(xù)比較后繼字符		{  			++i;			++j;		}		else // 指針后退重新開(kāi)始匹配 		{			i = i - j + 2;			j = 1;		}	}	if (j > T[0]) 		return i - T[0];	else 		return 0;} // Index
下面分析下：
這里先說(shuō)明下，這個(gè)S[0],T[0]這個(gè)地方存儲(chǔ)了整個(gè)串的大小。
這個(gè)代碼的巧妙之處在于i=i-j+2和j=1這個(gè)地方，這個(gè)i=j-j+2，可以讓i進(jìn)行后移，也就是S后移，這里j=1,的意思如下：舉個(gè)例子，當(dāng)T中是ABC，而S是ABABABC，pos為1，那么j=1的作用就是清理，什么叫清理，意思就是當(dāng)發(fā)現(xiàn)S中只有前兩個(gè)字母相似，而沒(méi)有第三個(gè)，這時(shí)重新計(jì)數(shù)。當(dāng)然i也要進(jìn)行回溯。
下面這張圖，提現(xiàn)了這個(gè)過(guò)程（T='abcac'和主串S,pos=1）
這節(jié)就到這，下一節(jié)講解數(shù)據(jù)結(jié)構(gòu)里面的第一個(gè)難點(diǎn)：
KMP算法！