2

Есть функция хэшировния строки c символами A-Za-z0-9_. Как её обратить, чтобы можно было перебирать строки с одинаковым хэшем? Иными словами, нужно написать что-то наподобие генератора строк (до 15000) с одинаковым хэшем.

const int p = 31;
size_t operator()(const string& s) const {
    size_t hash = 0, p_pow = 1;
    for (size_t i = 0; i < s.size(); ++i) {
        hash += (s[i] - 'a' + 1) * p_pow;
        p_pow *= p;
    }
    return hash;
}
16
  • Ну вы же понимаете, что обычно при хэшировании теряется некоторое кол-во информации и обратное преобразование не является однозначным?
    – CrazyElf
    29 ноя 2021 в 10:55
  • 1
    Ну конкретно ту это даже не хеш, а представление слова в 31-разрядной системе (если буквы только маленькие латинские)
    – Alexey Ten
    29 ноя 2021 в 10:58
  • @AlexeyTen - точно, снова забыл уточнить про формат строк: латинский алфавит в обоих регистрах, цифры и нижнее подчёркивание
    – Eraston
    29 ноя 2021 в 11:00
  • 1
    Уберите слово хэш из вопроса. Это никакой не хэш (в стандартном понимании) и вы только вводите всех в заблуждение
    – Alexey Ten
    29 ноя 2021 в 11:05
  • 1
    @Eraston, вы хотите по заданному хэшу (для сомневающихся: то, что считает данный код называется хэшем (хэши бывают разные, но тут разговор не об этом)) получить одну строку (набор байт) или заданное количество разных строк? Кстати, есть ли какие-то ограничения на символы этих строк (да и сами строки (префиксы-суффиксы, повторы символов и т.п.)?
    – avp
    29 ноя 2021 в 11:14

2 ответа 2

5

Ваш «хэш» это просто полином вида S = an×31n + … + a1×31 + a0.

Где все ak имеют значения из списка -48…-39 (0-9), -31…-6 (A-Z), -1 (_) и 1…26 (a-z).

Для примера возьмём S = 20. Посчитаем остаток от деления на 31. S % 31 = 20. (Ну да, немножко тривиально). Очевидно что ak при k >= 1 никак не влияют на этот остаток. Смотрим какие значения a0 могут дать такой остаток. Это значения 20, -11 и -42. Т.е. первый символ нашей строки это t, U или 6.

не дописал…

10
  • Может, я могу понять то, что вы написали, но не совсем понимаю, от чего искать остаток от деления, и что он показывает. Но с этим можно разобраться. Другой вопрос, что 31^14 > 2^64... Но попробую сделать что-то с тем, о чём вы написали
    – Eraston
    29 ноя 2021 в 12:37
  • Посчитайте хеши от t, Ua и 6b. Если я правильно понимаю код, то они будут одинаковые.
    – Alexey Ten
    29 ноя 2021 в 12:40
  • Да, одинаковые.
    – Eraston
    29 ноя 2021 в 12:42
  • @Eraston берете хеш, считаете остаток от деления на 31, находите первый символ. Вычитаете из хеша этот остаток, делите полученную разность на 31 и опять ищете остаток от деления на 31. Получаете второй символ и т.д.. Когда в результате очередного вычитания получаете 0 - строка найдена. Если получаете отрицательное число, то прибавляете к нему 2^64 29 ноя 2021 в 13:29
  • Вот только ТС хочет получить не одну подходящую строку, а 15000. Как тут сделать "направленную" генерацию?
    – avp
    29 ноя 2021 в 16:00
0

В общем, выросло следующее. Не уверен, что приведённый код перебирает все доступные строки заданной длины, но может генерировать некоторое множество строк с одинаковым хэшем.

void recursiveSearch( size_t hash, std::string s ){
    if( hash == 0 ){
        // Строка найдена
        // ...
        return;
    }
    if( s.size() < 12 ) // Ограничить размер строки, иначе некая бесконечная строка может иметь ненулевой хэш
        for( auto q : ab ) // Для каждого символа алфавита
        {
            if( ( hash - q ) % 31 == 0 ) // Если символ подходящий
                // Искать подпоследовательность(-и)
                recursiveSearch( ( hash - q ) / 31, s + std::string( 1, static_cast<char>( q + 'a' - 1 ) ) );
        }
}

Группа вывода:

OPHRBCBBBBBBBBa OPHRBCBBBBBBBa OPHRBCBBBBBBa OPHRBCBBBBBa OPHRBCBBBBa OPHRBCBBBa OPHRBCBBa OPHRBCBa OPHRBCa OPHRBb

1
  • К сожалению, исходной поставленной задачи это не решает, в которой в std::unordered_set нужно добавить 15000 строк таких, чтобы время работы программы превысило 1,5 секунды, - по логике устройства хэш-таблицы, самый очевидный способ, добавлять те строки, хэш которых совпадает
    – Eraston
    29 ноя 2021 в 17:06

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.