C語言樸素模式匹配算法實(shí)例代碼
一、什么是字符串的模式匹配？
字符串模式匹配：在主串中找到與模式串相同的子串，并返回其所在位置。
注意：
①、子串——主串的一部分，一定存在。
②、模式串——不一定能在主串中找到
二、樸素模式匹配算法
主串長度為n，模式串長度為m。
樸素模式匹配算法：將主串中所有長度為m的子串依次與模式串匹配對比，直到找到一個(gè)完全匹配的子串，或所有的子串都不匹配為止。
最多對比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è)⼦串都要對⽐ 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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了六大排序算法-插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序，需要學(xué)習(xí)的小伙伴可以參考這篇文章2021-08-08
VC實(shí)現(xiàn)讓關(guān)閉按鈕成灰色不可用的方法
這篇文章主要介紹了VC實(shí)現(xiàn)讓關(guān)閉按鈕成灰色不可用的方法,比較實(shí)用的一個(gè)特殊功能,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了C++中繼承基類與派生類的區(qū)別,面向?qū)ο蟪绦蛟O(shè)計(jì)中最重要的一個(gè)概念是繼承。繼承允許我們依據(jù)另一個(gè)類來定義一個(gè)類，這使得創(chuàng)建和維護(hù)一個(gè)應(yīng)用程序變得更容易,需要的朋友可以參考下2023-05-05
C?數(shù)組允許定義可存儲(chǔ)相同類型數(shù)據(jù)項(xiàng)的變量，結(jié)構(gòu)是?C?編程中另一種用戶自定義的可用的數(shù)據(jù)類型，它允許你存儲(chǔ)不同類型的數(shù)據(jù)項(xiàng)，本篇讓我們來了解C?的結(jié)構(gòu)體2022-02-02
Qt的Qss是一種用于定義用戶界面的樣式表語言，本文主要介紹了Qt的Qss用法小結(jié)，非常具有實(shí)用價(jià)值，需要的朋友可以參考下2023-06-06
在Vitis?IDE中如何使用第三方庫?libtiff?保存?tiff?文件
這篇文章主要介紹了在Vitis?IDE中如何使用第三方庫?libtiff?保存?tiff?文件,本文通過圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-07-07
在編程時(shí)我們有時(shí)總希望自己產(chǎn)生一個(gè)隨機(jī)數(shù)字，以供使用，那么下面介紹rand函數(shù)的使用，有需要的可以參考學(xué)習(xí)。2016-08-08
這篇文章主要介紹了C++ CopyFile,MoveFile用法案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
OpenCV實(shí)現(xiàn)圖像轉(zhuǎn)換為漫畫效果
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)圖像轉(zhuǎn)換為漫畫效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-08-08
Windows上Qt配置OpenCV的詳細(xì)教程(避坑必看)
這篇文章詳細(xì)介紹了在Windows上使用Qt配置OpenCV的步驟,包括軟件安裝、環(huán)境變量配置、Qt項(xiàng)目配置以及通過創(chuàng)建pri文件簡化OpenCV庫的添加過程,并提供了一個(gè)簡單的測試案例來驗(yàn)證配置是否成功,需要的朋友可以參考下2025-02-02