Borland字符串::發現bug

Question

我支持使用Borland C++ Builder 5.02（從1997年）編寫的C++應用程序。在Borland的string類的find（）方法並不表現我怎麼會想到：

#include <cstring> 
#include <iostream> 

int main (int argc, char *argv[]) 
{ 
    string needle = "length == eighteen"; 
    string haystack = "<" + needle + ">"; 
    if (haystack.find(needle) != NPOS) 
     cout << "Found it!" << endl; 
    else 
     cout << "Not found" << endl; 

    return 0; 
} 

這個節目輸出Not found。如果我將針更換爲更短的物體，則輸出Found it!。如果我交換尖括號中的其他字符，它會找到它。空格工作，但括號也沒有。

請注意，我在這裏使用Borland字符串庫：如果我使用#include <string>並使用std::string，那麼它的工作原理與我所期望的完全相同。不幸的是，改變整個應用程序來使用STL字符串並不是一個可行的答案！

從文檔似乎Borland公司進行字符串搜索基於散列的算法。我無法找到更多有關這方面的細節，而且我已經完成了反彙編，但沒有太多明智之舉。

我覺得很難相信，這是真的在字符串庫中的錯誤，特別是因爲如果它是那麼我會希望能夠找到關於它的文章什麼的。我找不到任何此類信息。

但是，我已經用完了想法！這是一個已知的錯誤？有沒有修復？

編輯：再看看反彙編，我認爲它試圖做一些像拉賓卡普算法，其中散列函數計算國防部33554393（最大質數< 2^25）。它很可能是基數爲32的多項式哈希函數（即a_0 + 32 a_1 + 32^2 a_2 + .. + 32^n a_n），但這只是一種預感。聽起來像Daniel Fischer建議的那樣可能會出現溢出。

Answer 1

我發現從1998年建議Borland的執行搜索的字符串的引用有錯誤：

https://groups.google.com/forum/?fromgroups=#!searchin/borland.public.cpp.language/cstring $ 20bug/borland.public.cpp.language/XBzjaJmCYpk/gtMPm-j8jugJ

另外，似乎在歷史某一時刻，C++ commitee決定字符串類將是標準的C++的一部分，並且爲c_string的字符串類就是一個殘：

https://groups.google.com/forum/?fromgroups=#!searchin/borland.public.cpp.language/borland $ 20cstring/borland.public.cpp.language/2psY2seRmS4/ywVrqwU1C2wJ

Answer 2

您沒有使用Borland字符串庫。 String（大寫字母S）是Borland字符串類。 string（小寫字母s），與std::string完全相同，是STL字符串類，它不是Borland實現（BCB5中的STL是RogueWave STL）。您使用#include <cstring>可能會將std::string帶入全局命名空間，這就是您的代碼編譯的原因。但你真的應該使用#include <string>和std::string。至於NPOS，您應該使用string::npos來代替，因爲string::find()實際上返回的是這個值。

#include <cstring> 
#include <iostream> 

int main (int argc, char *argv[]) 
{ 
    string needle = "length == eighteen"; 
    string haystack = "<" + needle + ">"; 
    if (haystack.find(needle) != string::npos) 
     cout << "Found it!" << endl; 
    else 
     cout << "Not found" << endl; 

    return 0; 
} 

或者：

#include <string> 
#include <iostream> 

int main (int argc, char *argv[]) 
{ 
    std::string needle = "length == eighteen"; 
    std::string haystack = "<" + needle + ">"; 
    if (haystack.find(needle) != std::string::npos) 
     std::cout << "Found it!" << std::endl; 
    else 
     std::cout << "Not found" << std::endl; 

    return 0; 
} 

Answer 3

如果您有原始BC++ 5.02安裝盤，串類源下發現BC5 \ SOURCE \ RTL \ SOURCE \ STRING。

這裏是從字符串的代碼的摘錄:: find_case_index（）函數（由字符串稱爲:: find（）方法）：

const long q = 33554393L; 
const long q32 = q<<5; 

size_t testlength = length() - startindex; 
size_t patternlength = patl = strlen(cp); 
if(testlength < patternlength) 
    return NPOS; 
if(patternlength == 0) 
    return 0; 

long patternHash = 0; 
long testHash = 0; 

const char _FAR *testP = c_str()+startindex; 
const char _FAR *patP = cp; 
long x = 1; 
size_t i = patternlength-1; 

while(i--) 
    x = (x<<5)%q; 

for(i=0; i<patternlength; i++) 
    { 
    patternHash = ((patternHash<<5) + *patP++ ) % q; 
    testHash = ((testHash <<5) + *testP++) % q; 
    } 

testP = c_str()+startindex; 
const char _FAR *end = testP + testlength - patternlength; 

while (1) 
    { 

    if(testHash == patternHash) 
     if(!get_paranoid_check_flag() || 
      !strncmp(testP, cp, patternlength)) 
      return (size_t)(testP-c_str()); 

    if(testP >= end) 
     break; 

    // Advance & calculate the new hash value: 
    testHash = (testHash + q32 - *testP * x    ) % q; 
    testHash = ((testHash<<5) + *(patternlength + testP++)) % q; 
    } 
return NPOS;   // Not found.