国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計 > 正文

4.3串的模式匹配算法(BF算法)

2019-11-11 05:25:13
字體:
供稿:網(wǎng)友

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

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

算法4.5:

下面是書中的偽代碼:

int Index(SString S, SString T, int pos) { 	// 返回子串T在主串S中第pos個字符之后的位置。	// 若不存在,則函數(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 // 指針后退重新開始匹配 		{			i = i - j + 2;			j = 1;		}	}	if (j > T[0]) 		return i - T[0];	else 		return 0;} // Index

下面分析下:

這里先說明下,這個S[0],T[0]這個地方存儲了整個串的大小。

這個代碼的巧妙之處在于i=i-j+2和j=1這個地方,這個i=j-j+2,可以讓i進行后移,也就是S后移,這里j=1,的意思如下:舉個例子,當(dāng)T中是ABC,而S是ABABABC,pos為1,那么j=1的作用就是清理,什么叫清理,意思就是當(dāng)發(fā)現(xiàn)S中只有前兩個字母相似,而沒有第三個,這時重新計數(shù)。當(dāng)然i也要進行回溯。

下面這張圖,提現(xiàn)了這個過程(T='abcac'和主串S,pos=1)

這節(jié)就到這,下一節(jié)講解數(shù)據(jù)結(jié)構(gòu)里面的第一個難點:

KMP算法!


發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 南澳县| 黄骅市| 新绛县| 江华| 江北区| 凉山| 赫章县| 贵港市| 富源县| 上犹县| 大化| 宿州市| 积石山| 顺昌县| 景洪市| 永清县| 务川| 托克逊县| 武陟县| 从化市| 巫溪县| 嘉义县| 台中市| 白城市| 平利县| 西充县| 建始县| 岳西县| 莒南县| 北票市| 施秉县| 青州市| 买车| 汨罗市| 长宁县| 合阳县| 石柱| 双鸭山市| 故城县| 玉屏| 广东省|