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.