導航:首頁 > 源碼編譯 > horspool演算法c語言

horspool演算法c語言

發布時間:2023-06-01 07:19:08

A. 實現Horspool演算法並在文本「BESS KNEW ABOUT BAOBABS」中查找模式「BAOBAB」輸出比較次數的屏幕截圖

horspool和kmp的思路相似,都是通過預處理模式串來找到失配函數(轉移函數),進而避免重復運算。演算法平均時間復雜度是O(N),但在最壞的情況下,會達到O(MN)。下面的代碼列印出了每次轉移的結果,方便了解horspool的過程。

#include<bits/stdc++.h>
usingnamespacestd;

constchar*text="BESSKNEWABOUTBAOBABS";
constchar*pattern="BAOBAB";
intT[256];//轉移函數

voidinit(constchar*pattern)
{
intsz=strlen(pattern);
for(inti=0;i<256;++i)T[i]=sz;
for(inti=0;i<sz-1;++i)T[pattern[i]]=sz-1-i;
}

intcalc()
{
intsz_text=strlen(text),sz_pattern=strlen(pattern);

inttot=0;悄帶//比較次數
intskip=0;//窗口左端點
while(sz_text運氏-skip>=sz_pattern){
//horspool的過程
printf("%s ",text);
for(inti=0;i<skip;++i)putchar('');
printf("%s ",pattern);

inti=sz_pattern-1;
while(text[skip+i]==pattern[i]){
++tot;//比較成功

if(i==0)returntot;
--i;
}
++tot;//比較失敗

skip=skip+T[text[skip+啟悄蘆sz_pattern-1]];
}
returntot;
}

intmain()
{
//對pattern進行預處理
init(pattern);

//horspool
printf("%d ",calc());

return0;
}

運行結果:

閱讀全文

與horspool演算法c語言相關的資料

熱點內容
農夫山泉app登不上去是什麼原因 瀏覽:432
如何趕走程序員 瀏覽:910
用支付寶登錄阿里雲伺服器 瀏覽:877
阿里雲伺服器怎麼更改ip 瀏覽:643
pvp和普通伺服器有什麼區別 瀏覽:706
pc收銀台系統源碼 瀏覽:624
程序員老公要加班 瀏覽:961
51單片機控制的超聲波 瀏覽:827
2021去水印最新源碼 瀏覽:232
ug編程刀具號重復 瀏覽:960
空當接龍演算法 瀏覽:609
可壓縮流體非恆定二維流動 瀏覽:695
天龍八部網單沒有找到技能文件夾 瀏覽:861
android串口程序 瀏覽:833
上海機器人程序員 瀏覽:914
兩台阿里雲伺服器如何拷貝 瀏覽:170
阿里媽媽淘寶聯盟需要什麼app 瀏覽:368
什麼人可以做編程員 瀏覽:359
網盤會員加速是在線解壓嘛 瀏覽:109
單片機按鍵匯編程序 瀏覽:729