4

我支持使用 Borland C++ Builder 5.02（从 1997 年开始）编写的 C++ 应用程序。Borland 字符串类的 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 使用基于哈希的算法进行字符串搜索。我找不到有关此的更多详细信息，并且我已经完成了拆卸，但并不聪明。

我很难相信这真的是字符串库中的一个错误，特别是因为如果是这样的话，我希望能够找到一篇文章或关于它的东西。我找不到任何此类信息。

但是，我已经没有想法了！这是一个已知的错误？有解决办法吗？

编辑：再次查看反汇编后，我认为它正在尝试执行类似 Rabin-Karp 算法的操作，其中哈希函数的计算方式为 mod 33554393（最大素数 < 2^25）。它很可能是底数为 32 的多项式哈希函数（即 a_0 + 32 a_1 + 32^2 a_2 + .. + 32^n a_n），但这只是一种预感。正如 Daniel Fischer 所建议的那样，听起来可能会溢出。

4

3 回答 3

2

我发现 1998 年的参考资料表明 Borland 搜索字符串的实现有一个错误：

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

此外，似乎在历史上的某个时刻，C++ 委员会决定字符串类将成为标准 C++ 的一部分，而 cstring 的字符串类是这个的残余：

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

于 2013-04-13T20:12:33.517 回答
2

如果您有原始的BC++ 5.02 安装盘，则可以在BC5\SOURCE\RTL\SOURCE\STRING 下找到字符串类源。

以下是 string::find_case_index() 函数（由 string::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.
于 2013-04-14T07:40:26.563 回答
1

您没有使用 Borland 字符串库。 String（大写 S）是 Borland 字符串类。string（小写的 s），与 完全相同std::string，是 STL 字符串类，它不是 Borland 实现（BCB5 中的 STL 是 RogueWave STL）。您的使用#include <cstring>可能会带入std::string全局名称空间，这就是您的代码编译的原因。但是你真的应该使用#include <string>andstd::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;
}
于 2013-04-13T18:11:37.883 回答