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

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;
}

運行結果：

熱點內容

農夫山泉app登不上去是什麼原因發布：2025-03-14 13:50:12 瀏覽：432

如何趕走程序員發布：2025-03-14 13:50:02 瀏覽：910

用支付寶登錄阿里雲伺服器發布：2025-03-14 13:31:22 瀏覽：877

阿里雲伺服器怎麼更改ip 發布：2025-03-14 13:12:16 瀏覽：643

pvp和普通伺服器有什麼區別發布：2025-03-14 12:55:43 瀏覽：706

pc收銀台系統源碼發布：2025-03-14 12:50:45 瀏覽：624

程序員老公要加班發布：2025-03-14 12:42:10 瀏覽：961

51單片機控制的超聲波發布：2025-03-14 12:33:36 瀏覽：827

2021去水印最新源碼發布：2025-03-14 12:32:03 瀏覽：232

ug編程刀具號重復發布：2025-03-14 12:18:18 瀏覽：960

空當接龍演算法發布：2025-03-14 12:17:43 瀏覽：609

可壓縮流體非恆定二維流動發布：2025-03-14 12:11:08 瀏覽：695

天龍八部網單沒有找到技能文件夾發布：2025-03-14 12:03:35 瀏覽：861

android串口程序發布：2025-03-14 11:53:42 瀏覽：833

上海機器人程序員發布：2025-03-14 11:49:36 瀏覽：914

兩台阿里雲伺服器如何拷貝發布：2025-03-14 11:40:48 瀏覽：170

阿里媽媽淘寶聯盟需要什麼app 發布：2025-03-14 11:39:33 瀏覽：368

什麼人可以做編程員發布：2025-03-14 11:23:45 瀏覽：359

網盤會員加速是在線解壓嘛發布：2025-03-14 11:23:00 瀏覽：109

單片機按鍵匯編程序發布：2025-03-14 11:20:51 瀏覽：729

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

horspool演算法c語言

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