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 文字列ライブラリを使用していることに注意してください。代わりに I#include <string>を使用するstd::stringと、期待どおりに動作します。残念ながら、STL 文字列を使用するようにアプリケーション全体を変更することは、実現可能な答えではありません。

ドキュメントによると、Borland は文字列検索にハッシュ ベースのアルゴリズムを使用しているようです。これについてこれ以上の詳細を見つけることができず、分解を進めましたが、それほど賢明ではありません.

これが本当に文字列ライブラリのバグであるとはとても信じがたいと思います。もしそうなら、それについての記事か何かを見つけることができると期待しているからです。そのような情報は見つかりません。

しかし、私はアイデアを使い果たしました！これは既知のバグですか? 修正はありますか？

編集:逆アセンブリをもう一度見てみると、ハッシュ関数が mod 33554393 (最大素数 < 2^25) で計算される Rabin-Karp アルゴリズムのようなことをしようとしていると思います。これは、底が 32 の多項式ハッシュ関数 (つまり、a_0 + 32 a_1 + 32^2 a_2 + .. + 32^n a_n) である可能性がありますが、それはただの予感です。Daniel Fischer が示唆したように、オーバーフローの可能性があるように思えます。

4

3 に答える 3

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 に答える
2

Borland の文字列検索の実装にバグがあることを示唆する 1998 年の参考文献を見つけました。

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 に答える