国产探花免费观看_亚洲丰满少妇自慰呻吟_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ā)表
主站蜘蛛池模板: 稻城县| 久治县| 疏勒县| 英吉沙县| 蕉岭县| 玉环县| 鞍山市| 连南| 新安县| 榆林市| 玛纳斯县| 搜索| 固镇县| 金乡县| 五指山市| 邢台市| 北京市| 乌鲁木齐市| 鹤庆县| 临沧市| 正安县| 重庆市| 宜昌市| 根河市| 珠海市| 莎车县| 朔州市| 通城县| 墨玉县| 静安区| 灵丘县| 邓州市| 永新县| 淅川县| 龙江县| 西乡县| 滦平县| 厦门市| 甘洛县| 定结县| 桓仁|