C語言中怎么實(shí)現(xiàn)樸素模式匹配算法

這篇文章主要介紹“C語言中怎么實(shí)現(xiàn)樸素模式匹配算法”，在日常操作中，相信很多人在C語言中怎么實(shí)現(xiàn)樸素模式匹配算法問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C語言中怎么實(shí)現(xiàn)樸素模式匹配算法”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

一、什么是字符串的模式匹配？

字符串模式匹配：在主串中找到與模式串相同的子串，并返回其所在位置。

注意：

①、子串——主串的一部分，一定存在。

②、模式串——不一定能在主串中找到

二、樸素模式匹配算法

主串長(zhǎng)度為n，模式串長(zhǎng)度為m。

樸素模式匹配算法：將主串中所有長(zhǎng)度為m的子串依次與模式串匹配對(duì)比，直到找到一個(gè)完全匹配的子串，或所有的子串都不匹配為止。

最多對(duì)比n-m+1個(gè)子串

（一）通過數(shù)組下標(biāo)實(shí)現(xiàn)樸素模式匹配算法

若當(dāng)前?串匹配失敗，則主串指針 i 指向下?個(gè)?串的第?個(gè)位置，模式串指針 j 回到模式串的第?個(gè)位置

若 j > T.length，則當(dāng)前?串匹配成功，返回當(dāng)前?串第?個(gè)字符的位置 —— i - T.length

int Index(SString S, SString T){
	int i=1,j=1;
	while(i <= S.length && j<=T.length){
		if(S.ch[i]==T.ch[j]){
			++i;
			++j;	//繼續(xù)比較后繼字符
		}
		else{
			i=i-j+2;
			j=1;	//指針后退重新開始匹配
		}
	}
	if(j > T.length)
		return i-T.length;
	else
		return 0;
}

（二）時(shí)間復(fù)雜度

設(shè)主串?度為 n，模式串?度為 m，則

①、最壞時(shí)間復(fù)雜度 = O(nm)

②、最好時(shí)間復(fù)雜度 = O(n) 1. 最壞時(shí)間復(fù)雜度O(nm)

最壞的情況，每個(gè)?串都要對(duì)? m 個(gè)字符，共 n-m+1 個(gè)?串，復(fù)雜度 = O((n-m+1)m) = O(nm)

注：很多時(shí)候，n >> m

2. 最好時(shí)間復(fù)雜度O(n)

最好的情況，每個(gè)?串的第?個(gè)字符就匹配失敗，共 n-m+1 個(gè)?串，復(fù)雜度 = O(n-m+1) = O(n)

注：很多時(shí)候，n >> m

到此，關(guān)于“C語言中怎么實(shí)現(xiàn)樸素模式匹配算法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！