hrbustoj 1551:基礎データ構造——文字列2ウイルスII(文字列マッチング、BMアルゴリズム練習)

基礎データ構造——文字列2ウイルスIITime Limit:1000 MS Memory Limit:10240 KTotal Submit:284(138 users)Total Acceptted:177(135 users)Rating:Special Jdge:NoDescriptionは、コンピュータウイルスの概念が提案されてから、ウイルスの種類が次々と出てきます.今はただのウイルスはウイルス対策ソフトから逃げられない.そのため、現在のウイルスはいくつかの文字を隠して、クリアする目的を達成します.連続文字列として知られている「bkpstr」はウイルスコードの一部です.与えられた文字列の中にウイルスコードが含まれているかどうかを分析してください.
Input本題は複数のテストデータがあり、各グループのデータに対して文字列Str(長さが100を超えない)を入力し、ファイル終了まで処理します.
Output文字列にウイルスコードが含まれている場合、Warningを出力して改行します.さもなければSafeを出力して改行します.
Sample Input 1234 55676 sa
Sample Output Safe
Author楊和禹@HRBUST
 
文字列が一致します.
私が使ったのはBMアルゴリズムで、BMアルゴリズムはBFアルゴリズムの最適化で、亜線形整合アルゴリズムです.BFより少し早いです.
コード:

 1 #include <stdio.h>

 2 int BM_index(char t[],char s[])    //          

 3 {  4     int i,j,lt,ls;  5     for(lt=0;t[lt];lt++);    //    

 6     for(ls=0;s[ls];ls++);  7     //BM  

 8     for(i=ls-1;i>=lt-1;i--)  9         if(s[i]==t[lt-1]){ 10             for(j=2;j<=lt;j++) 11                 if(t[lt-j]!=s[i-j+1]) 12                     break; 13             if(j>lt) break; 14  } 15     if(i>=lt-1) return i-lt+1; 16     return -1; 17 } 18 int main() 19 { 20     char t[20]="bkpstor",s[110]; 21     while(scanf("%s",s)!=EOF){ 22         if(BM_index(t,s)==-1) 23             printf("Safe
"); 24         else 

25             printf("Warning
"); 26  } 27     return 0; 28 }

 
フリーコード:www.cnblogs.com/ym 2 013