【資料結構】圖解串的樸素模式比對（C語言）

模式比對：子串定位運算，在主串中找出子串出現的位置。

假設我們要從下面的主串S=“goodgoogle”中，找到T=“google”這個子串的位置。我們通常需要下面的步驟。

1、主串S第一位開始，S與T前三個字母比對成功，但是S第四個字母是d而T的是g。第一位比對失敗。下圖所示，其中豎直連線表示相等，閃電狀彎折線表示不相等。

2、主串S第二位開始，主串S首字母是o，要比對的T首字母是g，比對失敗。

3、主串S從第三位開始，主串S首字母是o，要比對的T首字母是g，比對失敗。

4、主串S第四位開始，主串S首字母是d，要比對的T首字母是g，比對失敗。

5、主串S第五位開始，S與T，6個字母全比對，比對成功。

簡單的說，就是對主串的每一個字元作為子串開頭，要與比對的字元串進行比對。對主串做大循環，每個字元開頭做T的長度的小循環，直到比對成功或者全部周遊完成為止。

//傳回子串T在主串S中第pos個字元之後的位置。若不存在，傳回0
//T非空，1<=pos <=StrLength(S)
int Index(Sitnrg S,String T,int pos)
{
	/*
	i用于主串S中目前下标位置，若pos不為1，則從pos位置開始比對
	*/
	int i = pos;
	int j = 1; //j用于子串T中目前位置下标值

	while(i <= S[0] && j <= T[0]) //i小于長度且j小于T的長度時循環
	{
		if(S[i] == T[i])  //字母相等則繼續
		{
			++i;
			++j;
		}
		else
		{
			i = i - j+ 2; //退回到上次比對首位的下一位
			j = 1;       //j退回到子串T的首位
		}
	}
	if(j > T[0])
		return i - T[0];
	else
		return 0;
}
           

分析一下，最好的情況就是一開始就比對成功，時間複雜發為O(1),最壞的情況就是每次比對不成功的比對都發生在串T的最後一個字元。