文字列アルゴリズム--Sundayアルゴリズム

1.SundayアルゴリズムはDanielです. M.Sundayは1990年にBMアルゴリズムよりも速い検索アルゴリズムを提案しました. 
2.SundayアルゴリズムはBMアルゴリズムと似ています.Sundayアルゴリズムは往後からマッチします.
   マッチに失敗したときに注目するのは、テキスト列の最後の文字にマッチする次の文字です.
   マッチした列に文字が現れない場合はそのままスキップします.すなわち移動ステップ= 列の長さに合わせる＋ 1;
   そうでないと、BMアルゴリズムと同じように移動ステップサイズ=列の一番右側の文字と最後までの距離+1が一致します. 
 3.例を挙げると次のようになります

//pos=0;

//   ：abcdacdaahfacabcdabcdeaa

//   ：abcde 

//      a-e    ，         pos+len2       ，    。 



//   ：abcdacdaahfacabcdabcdeaa

//   ：   abcde 

//pos=3; 

//      d-a    ，         pos+len2       ，    。 



//   ：abcdacdaahfacabcdabcdeaa

//   ：        abcde 

//pos=8; 

//      h-b    ，         pos+len2       ，    。 



//   ：abcdacdaahfacabcdabcdeaa

//   ：           abcde 

//pos=13; 

//      c-b    ，         pos+len2       ，    。 



//   ：abcdacdaahfacabcdabcdeaa

//   ：                 abcde 

//pos=17; 

//             

 
コードのデモは以下の通りです.

 1 #include <iostream>   

 2 #include <cstring>   

 3 using namespace std;   

 4 

 5 char T[10001];

 6 char P[26];

 7 int next[26];

 8 

 9 int sunday(const char* T, const char* P)   

10 {   

11     int len1=strlen(T);   

12     int len2=strlen(P);   

13     memset(next,0,sizeof(next)); 

14     

15     for(int j=0; j<26;++j)   

16         next[j]=len2+1;   

17     for(j=0; j<len2;++j) 

18     {

19         next[P[j]-'a']=len2-j; //             +1

20         //cout<<"next["<<P[j]-'a'<<"]="<<next[P[j]-'a']<<endl;

21     }    

22     //  :p[]="abcedfb"   

23     //next = {7 6 5 4 3 2 1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8}

24     

25     int pos = 0;   

26     while(pos<(len1-len2+1)) //       

27     {   

28         int i=pos;   

29         int j;   

30         for(j=0;j<len2;++j,++i)   

31         {   

32             if(T[i]!=P[j])  //      ,       

33             {   

34                 pos+= next[T[pos + len2]-'a'];  

35                 //cout<<"pos="<<pos<<endl<<endl;

36                 break;   

37             }   

38         }   

39         if(j==len2)   

40             return pos;   

41     }   

42     return -1;   

43 }    

44 int main()   

45 {    

46     char T[]="abcdacdaahfacabcdabcdeaa";

47     char P[]="abcde"; 

48     while(scanf("%s%s",T,P)!=EOF)

49         cout<<sunday(T,P)<<endl;   

50     return 0;   

51 }