C語言樸素模式匹配算法實(shí)例代碼
一、什么是字符串的模式匹配？
字符串模式匹配：在主串中找到與模式串相同的子串，并返回其所在位置。
注意：
①、子串——主串的一部分，一定存在。
②、模式串——不一定能在主串中找到
二、樸素模式匹配算法
主串長(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
總結(jié)
到此這篇關(guān)于C語言樸素模式匹配算法的文章就介紹到這了,更多相關(guān)C語言樸素模式匹配算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語言求連續(xù)最大子數(shù)組和的方法,包含了數(shù)組的常見操作及相關(guān)技巧,需要的朋友可以參考下2014-09-09
LeetCode 單調(diào)棧內(nèi)容小結(jié)
這篇文章主要介紹了LeetCode 單調(diào)棧內(nèi)容小結(jié),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++中string轉(zhuǎn)換為char*類型返回后亂碼問題解決
這篇文章主要介紹了C++中string轉(zhuǎn)換為char*類型返回后亂碼問題解決,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要為大家介紹了C語言判斷語句和if語句形式及多層if使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09
C++中對(duì)C語言結(jié)構(gòu)體用法的擴(kuò)充
今天小編就為大家分享一篇關(guān)于C++中對(duì)C語言結(jié)構(gòu)體用法的擴(kuò)充，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將和大家一起聊聊C語言中單鏈表的常用操作，感興趣的可以學(xué)習(xí)一下2022-07-07
形參出現(xiàn)在函數(shù)定義中，在整個(gè)函數(shù)體內(nèi)都可以使用， 離開該函數(shù)則不能使用。實(shí)參出現(xiàn)在主調(diào)函數(shù)中，進(jìn)入被調(diào)函數(shù)后，實(shí)參變量也不能使用，形參和實(shí)參的功能是作數(shù)據(jù)傳送。發(fā)生函數(shù)調(diào)用時(shí)， 主調(diào)函數(shù)把實(shí)參的值傳送給被調(diào)函數(shù)的形參從而實(shí)現(xiàn)主調(diào)函數(shù)向被調(diào)函數(shù)的數(shù)據(jù)傳送2023-02-02
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)幀間差分法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
C++使用new和delete進(jìn)行動(dòng)態(tài)內(nèi)存分配與數(shù)組封裝
這篇文章主要介紹了C++使用new和delete進(jìn)行動(dòng)態(tài)內(nèi)存分配與數(shù)組封裝，運(yùn)行期間才能確定所需內(nèi)存大小，此時(shí)應(yīng)該使用new申請(qǐng)內(nèi)存，下面我們就進(jìn)入文章學(xué)習(xí)具體的操作方法，需要的小伙伴可以參考一下2022-03-03
這篇文章主要為大家介紹了如何利用C語言實(shí)現(xiàn)原神抽卡的小游戲，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-04-04