加快Boyer-Moore-Horspool字符串搜索的實現

-1

在C++中實現BMH算法時遇到了一些問題。加快Boyer-Moore-Horspool字符串搜索的實現

下面的代碼：

#define Nm 2000005 
int D[256]; 
char To[Nm],P[Nm],*T; 
int Tl,Pl; 
int cont; 
void initialize_Lenght() 
{ 
    Tl=strlen(To); 
    Pl=strlen(P); 
    T=To; 
} 
void compute_D() 
{ 
    for(int i=0;i<256;i++) 
     D[i]=Pl; 
    for(int i=0;i<Pl;i++) 
     D[P[i]]=Pl-i; 
} 
void Boyer_Moore() 
{ 
    int i; 

    while (Tl>=Pl)  
    { 
     for(i=Pl-1;T[i]==P[i]&&i>=0;i--) 
      if(i==0) 
      { 
       if(cont<1000) 
        v[cont]=(T-To); // I also have to store the first 1000 values 
       cont++; 
      } 
      Tl -= D[T[i+1]]; 
      T += D[T[i+1]]; 
    } 
}

它適用於大多數的例子，但也有一些例子，不工作（僅我發現迄今是從不同的來源下載龐大的測試的）。

我想知道我在做什麼錯在哪裏（我真的不想要代碼）。

編輯：由於意見

你有什麼想法，我怎麼能做出這樣的算法的運行速度沒有實現它的全博耶 - 穆爾的版本？

來源

2013-01-16 Taigi100

你可以更具體地瞭解哪些輸入無效，以什麼方式無效？否則我們將不得不重複所有的努力！ – Eevee

我不知道什麼不起作用，因爲測試文件不是很大，但我要上傳它。 – Taigi100

是的，我是愚蠢愚蠢的...我的問題是一個愚蠢的，如果它<1000而不是<= 1000 ... – Taigi100

的測試中

for(i=Pl-1;T[i]==P[i]&&i>=0;i--)

的順序是錯誤的。完成匹配後，在比較T[-1]到P[-1]之後，檢查索引是否可接受。

如果發生在最後圖案字符不匹配，根據該不必存在（如果該圖案端與文本端部對準）的字符

Tl -= D[T[i+1]]; 
T += D[T[i+1]];

跳過。

來源

2013-01-16 20:39:47

我已經意識到並通過在for中添加if來修復它，而不是在for-test中進行測試。 – Taigi100

加快Boyer-Moore-Horspool字符串搜索的實現

回答

相關問題