亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C語言樸素模式匹配算法實例代碼

 更新時間:2021年06月04日 10:47:49   作者:bfhonor  
樸素模式匹配算法也稱為布魯特-福斯算法,感覺很是高大上,但是實現(xiàn)起來很簡單。這篇文章主要給大家介紹了關(guān)于C語言樸素模式匹配算法的相關(guān)資料,需要的朋友可以參考下

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

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

注意:

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

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

 

二、樸素模式匹配算法

主串長度為n,模式串長度為m。

樸素模式匹配算法:將主串中所有長度為m的子串依次與模式串匹配對比,直到找到一個完全匹配的子串,或所有的子串都不匹配為止。

最多對比n-m+1個子串

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

若當前⼦串匹配失敗,則主串指針 i 指向下⼀個⼦串的第⼀個位置,模式串指針 j 回到模式串的第⼀個位置

j > T.length,則當前⼦串匹配成功,返回當前⼦串第⼀個字符的位置 —— 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;
}

(二)時間復(fù)雜度

設(shè)主串⻓度為 n,模式串⻓度為 m,則

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

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

最壞的情況,每個⼦串都要對⽐ m 個字符,共 n-m+1 個⼦串,復(fù)雜度 = O((n-m+1)m) = O(nm)

注:很多時候,n >> m

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

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

注:很多時候,n >> m

總結(jié)

到此這篇關(guān)于C語言樸素模式匹配算法的文章就介紹到這了,更多相關(guān)C語言樸素模式匹配算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言求連續(xù)最大子數(shù)組和的方法

    C語言求連續(xù)最大子數(shù)組和的方法

    這篇文章主要介紹了C語言求連續(xù)最大子數(shù)組和的方法,包含了數(shù)組的常見操作及相關(guān)技巧,需要的朋友可以參考下
    2014-09-09
  • LeetCode 單調(diào)棧內(nèi)容小結(jié)

    LeetCode 單調(diào)棧內(nèi)容小結(jié)

    這篇文章主要介紹了LeetCode 單調(diào)棧內(nèi)容小結(jié),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++中string轉(zhuǎn)換為char*類型返回后亂碼問題解決

    C++中string轉(zhuǎn)換為char*類型返回后亂碼問題解決

    這篇文章主要介紹了C++中string轉(zhuǎn)換為char*類型返回后亂碼問題解決,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-07-07
  • C語言判斷語句和if語句形式及多層if使用示例

    C語言判斷語句和if語句形式及多層if使用示例

    這篇文章主要為大家介紹了C語言判斷語句和if語句形式及多層if使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-09-09
  • C++中對C語言結(jié)構(gòu)體用法的擴充

    C++中對C語言結(jié)構(gòu)體用法的擴充

    今天小編就為大家分享一篇關(guān)于C++中對C語言結(jié)構(gòu)體用法的擴充,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解

    C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解

    鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將和大家一起聊聊C語言中單鏈表的常用操作,感興趣的可以學(xué)習(xí)一下
    2022-07-07
  • C語言形參與實參使用的差別講解

    C語言形參與實參使用的差別講解

    形參出現(xiàn)在函數(shù)定義中,在整個函數(shù)體內(nèi)都可以使用, 離開該函數(shù)則不能使用。實參出現(xiàn)在主調(diào)函數(shù)中,進入被調(diào)函數(shù)后,實參變量也不能使用,形參和實參的功能是作數(shù)據(jù)傳送。發(fā)生函數(shù)調(diào)用時, 主調(diào)函數(shù)把實參的值傳送給被調(diào)函數(shù)的形參從而實現(xiàn)主調(diào)函數(shù)向被調(diào)函數(shù)的數(shù)據(jù)傳送
    2023-02-02
  • OpenCV實現(xiàn)幀間差分法詳解

    OpenCV實現(xiàn)幀間差分法詳解

    這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)幀間差分法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-03-03
  • C++使用new和delete進行動態(tài)內(nèi)存分配與數(shù)組封裝

    C++使用new和delete進行動態(tài)內(nèi)存分配與數(shù)組封裝

    這篇文章主要介紹了C++使用new和delete進行動態(tài)內(nèi)存分配與數(shù)組封裝,運行期間才能確定所需內(nèi)存大小,此時應(yīng)該使用new申請內(nèi)存,下面我們就進入文章學(xué)習(xí)具體的操作方法,需要的小伙伴可以參考一下
    2022-03-03
  • 基于C語言編寫一個簡單的抽卡小游戲

    基于C語言編寫一個簡單的抽卡小游戲

    這篇文章主要為大家介紹了如何利用C語言實現(xiàn)原神抽卡的小游戲,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-04-04

最新評論