Borland string :: find bug
Я поддерживаю приложение C ++, написанное с использованием Borland C ++ Builder 5.02 (с 1997 года). Метод find () в классе строк Borland не ведет себя так, как я ожидал:
#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), но это всего лишь догадка. Похоже на возможное переполнение, как предложил Даниэль Фишер.
Решение
Я нашел ссылку от 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
Другие решения
Если у вас есть оригинальный установочный диск 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.
Вы не используете библиотеку строк Borland. String (заглавная S) — класс строк Borland. string (строчные буквы s), что точно так же, как std::string, является классом строки STL, который НЕ является реализацией Borland (STL в BCB5 был 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;
}
detector