Comments 19
Спасибо, жду Кнута-Морриса-Прата и префиксные/суфиксные деревья ;)
про то, как перейти от брутфорса к МП, а от МП к КМП хотел в следующий раз обзор сделать… вот только не знаю — есть ли смысл, поскольку:
1) есть хорошие визуализации, вроде этой (спасибо el777 )
2) немногим это будет полезно

хотя…
я конечно стараюсь писать то, как я это представляю, ознакомившись с другими источниками. может быть кому-то будет интересна мелочь, которую он не замечал (в принципе это и есть повод писать и читать статьи — менять систему отсчёта для знакомых вещей так сказать).

одним словом — попробую написать что-то интересное или неочевидное в давно известном алгоритме
Перенесите в «Алгоритмы», что ли… Такие вещи достойны того, чтоб появится на главной.
Да главное, чтоб было. А то ведь топики из личных блогов потом не найти будет, на сколько я знаю. Да и вообще, что теперь, блог «алгоритмы» не наполнять соответствующим контентом?
хм. мы читаем алгоритмы, а не эстетствуем по поводу оформления итп. Так что не думаю что вот так надо к этому критично относится :)
Плохая хеш функция.

f(ab) == f(ba)

private int GetHashOfString(string s)
{
int result = 0;
for (int i = 0; i < s.Length; i++)
{
result += s[i];
}
return result;
}

И как следствие дополнительный код, который выливается в проверке по символьно.

if (patternHash == substringHash)
{
bool success = true;
for (int j = 0; j < patternLength; j++)


Попробуйте в ХФ учитывать позицию символа, а не только его код. Временные затраты будут небольшие, а вот количество ложных проверок уменьшиться.

Пожалуйста, читайте внимательнее.

private int GetHashOfString(string s, int q, int b)
{
int result = 0;
int length = s.Length;

for (int i = 0; i < length; i++)
result = (b * result + s[i]) % q;
return result;
}

Разве умножение кода символа на экспоненциально зависящее от позиции этого самого символа может дать симметричную хеш-функцию?
«умножение кода символа на экспоненциально зависящее от позиции этого самого символа»
извините, имел в виду «умножение кода символа на экспоненциально зависящее от позиции этого самого символа число»

Что-то я не понимаю, откуда выгода в скорости в алгоритме с такой сложной хеш-функцией, когда надо инициализировать со-процессор, выполнить несколько арифметических операций для каждого символа, ведь количество тактов затраченных на эти действия будет больше, чем количество тактов затраченных на сравнение и условный переход.

Хотя… если думать в рамках быстрого процессорного кеша, содержащего данные от хеш-функции оригинала и сравнения и медленной оперативной памяти, то да, количество доступов к оперативной памяти сильно сокращается
м-м-м… как бы сказать :)

берём брутфорс: два вложенных цикла. Сложность перемножается. То есть O(n*m), где n — длина строки, а m — длина шаблона.

берём алгоритм Рабина-Карпа: Предварительные вычисления сложности O(m) и потом опять два цикла, причём вложенный практически не запускается в холостую. Если взять base и q очень большими (но всё же простыми) числами, влазящими в int32, то на практике внутренний цикл можно не запускать — с огромной вероятностью совпадение хеш-значений будет свидетельствовать о совпадении строк.

Таким образом, сложность алгоритма в среднем случае O(m+n), что меньше O(m*n). В худшем случае сложность будет O(n*m), хотя вероятность такого случая на практике крайне мала.
Первое приближение создано, чтобы быть приближением к финальному алгоритму…
стразу после этого приближения описывается, насколько оно неэффективно
там нет ни одной float-point операции, следовательно, и сопр использоваться не будет.
Согласен поповоду «слабой» хэш функции подбор будет работать быстрее, но хотелось бы увидеть тест для MD5 — сравнение брутфорса и описанного в топике метода, с длиной строки 7-8 символов.
А смысл? У криптографических хэш-функций и функций, используемых в подобных алгоритмах, совершенно разное назначение и характеристики.
Only those users with full accounts are able to leave comments. Log in, please.