導航:首頁 > 源碼編譯 > 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語言相關的資料

熱點內容
兩台阿里雲伺服器如何拷貝 瀏覽:170
阿里媽媽淘寶聯盟需要什麼app 瀏覽:368
什麼人可以做編程員 瀏覽:358
網盤會員加速是在線解壓嘛 瀏覽:109
單片機按鍵匯編程序 瀏覽:728
傳播學綱要pdf第二版 瀏覽:385
樂友進銷存有什麼app 瀏覽:554
顯示器維修pdf 瀏覽:618
qq支付時怎麼雙層加密 瀏覽:943
2008伺服器如何做安全 瀏覽:310
戴爾系統加密怎麼解密 瀏覽:469
手機app企業辦稅子賬戶是什麼 瀏覽:660
wps如何快速解壓 瀏覽:562
漢王pdf轉換 瀏覽:117
linux學習步驟 瀏覽:502
達內杭州java培訓 瀏覽:163
建垃圾壓縮站應符合的規定 瀏覽:973
安卓怎麼測量開機電壓 瀏覽:775
程序員素質大全 瀏覽:953
激戰伺服器不見了怎麼辦 瀏覽:983