Calcweb.ru

Информационный портал
21 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Как определить тип хеша по содержимому строки

HackWare.ru

Этичный хакинг и тестирование на проникновение, информационная безопасность

Как определить тип хеша

В статье «Хеши: определение типа, подсчёт контрольных сумм, нестандартные и итерированные хеши» мы уже знакомились с такими утилитами как hashID и HashTag, которые по строке хеша определяют, по какому алгоритму он был вычислен.

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

Прямо сейчас, на момент написания, активно развиваются две новые программы для идентификации типов хешей. Они поддерживают больше алгоритмов хеширования и просто во всём лучше старых инструментов. Данная статья посвящена знакомству с новыми инструментами по идентификации типа хеша.

Зачем нужны новые инструменты идентификации типа хеша?

hashID не поддерживается с марта 2015 года, hash-identifier не поддерживается с 2011 года, Dagon с июня 2018 года и findmyhash с 2011 года. Все они не имеют вовсе, или имеют неправильную, ошибочную поддержку современных хешей, таких как Keccak/SHA3/Blake2 и т. д. Также такой инструмент, как hash-identifier, который является полностью интерактивным, не имеет параметров и не удобен для использования в скриптах. findmyhash имеет очень ограниченный набор обнаруживаемых хешей. Самый интересный инструмент — hashID (для идентификации хеша), но, поскольку он не поддерживается более 5 лет, проблемы и открытые PR (Pull Request — запросы на внесение изменения в исходный код) накапливаются, ошибки не исправляются, а некоторые функции отсутствуют.

Это всё могло побудить авторов создать новые инструменты с возможностями отсутствующими в предшественниках.

Посмотрим на сравнительную таблицу инструментов по определению типа хеша:

  • Ref.: показ рядом с типом хеша соответствующее название режима hashcat и john the ripper
  • ✅: функция поддерживается
  • ❌: функция не поддерживается
  • ⭕️: функция частично поддерживается
  • 💎: язык программирования Ruby
  • 🐍: язык программирования Python
  • #️⃣: корректная поддержка современных хешей
  • 🔢: количество поддерживаемых хешей

Образцы хешей

Если вам нужны образцы хешей для поверки инструментов, то смотрите раздел «Где посмотреть примеры хешей».

Я отобрал несколько хешей для анализа:

  • SHA3-224
  • SHA3-512
  • PKZIP Master Key
  • CRC32
  • Keccak-512

Хеши необходимо заключать в одинарные кавычки!

Хеши могу включать в себя специальные символы, которые имеют для оболочки специальное значение. Особенно это важно если вы работаете в Linux. Если вы не будете это учитывать, то программа по определению типа хеша хоть и не сообщит об ошибке, но получит строку отличную от той, которую вы думали что ввели.

Причём даже в двойных кавычках оболочка трактует некоторые символы как специальные. Поэтому чтобы не экранировать их, поместите весь хеш в одинарные кавычки.

Необязательно помещать в кавычки хеши, состоящие только из букв и цифр, но я предпочитаю все хеши передавать в одинарных кавычках.

HAITI

HAITI (HAsh IdenTifIer) — это инструмент командной строки (и библиотека) для идентификации типа заданного хеша. Библиотека особенно хороша для написания скриптов, поскольку не нужно заключать инструмент командной строки в подпроцесс.

  • Определение типов 382+ хешей
  • Поддержка современных алгоритмов (SHA3, Keccak, Blake2 и прочее)
  • Краткая информация по использованию хеша с Hashcat и John the Ripper
  • Инструмент командной строки и библиотека
  • Цветной вывод

Полный список опций программы и инструкции по установке вы найдёте в карточке программы: https://kali.tools/?p=6638

Использование программы очень простое — укажите ваш хеш после имени программы:

Причём ОПЦИИ являются необязательными, поведение программы по умолчанию очень сбалансированной и в большинстве случаев вам не захочется менять его какими-либо дополнительными параметрами.

Среди вывода есть и правильный ответ: SHA3-512

В выводе HC — это сокращение для Hashcat, а последующие цифры (например, 1700, 17600 и так далее) это номера режимов в данной программе.

JtR — это сокращение от John the Ripper, а последующие строки — это название алгоритмов хешей для взлома в данной программе (raw-sha512, raw-sha3 и так далее).

Цвет очень хорошо улучшает читаемость вывода, особенно если он обширный. Если вы хотите отключить цветной вывод, то используйте опцию —no-color:

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

Если вы хотите только узнать тип хеша и информация о режимах hashcat и john the ripper для вас является излишней, то вы можете указать опцию —short для укороченного вывода:

Name-That-Hash

С января 2021 года, почти через два года после того, как началась работа над HAITI, появился проект под названием Name-That-Hash, потому что автору требовалась библиотека Python для Ciphey. Теперь есть два актуальных варианта для идентификации хеша.

Name That Hash определяет тип хеша. Программа поддерживает MD5, SHA256 и более 300 других хешей.

Особенности Name That Hash:

  • Рейтинги популярности — Сначала вы увидите самые популярные хеши.
  • Сводки хешей — Name-that-hash выведет краткую информацию об основах использования каждого хеша, позволяя вам сделать осознанный выбор.
  • Цветной вывод — контрастный и наглядный.
  • Вывод в JSON и в API — вы можете использовать Name-That-Hash в своём проекте, поскольку программа имеет API и интерфейс командной строки. Используйте вывод JSON или импортируйте программу как модуль Python!
  • Актуальна — Name-That-Hash — это проект 2021 года.
  • Продуманность — авторы продумали функции, интерфейс и опции с мыслью об удобстве использования.
  • Расширяемость — добавляйте новые хеши так быстро, как только сможете редактировать текстовый файл.
  • Работа с файлами — программа считывает построчно файл и проверяет тип каждого хеша.
  • Поиск хешей — экстремальный режим, который пытается выделить хеш даже если строка содержит мусор.
Читайте так же:
BrowserAddonsView — универсальный просмотрщик браузерных дополнений

Инструкцию по установке и полный список опций вы найдёте на странице https://kali.tools/?p=6626.

Для определения типа хеша укажите его с опцией -t (—text):

Хеши разбиты на две группы:

  • Most Likely — более вероятные варианты
  • Least Likely — менее вероятные варианты

Причём в этих группах они также отсортированы по частоте использования.

В выводе вы можете увидеть уже знакомые строки HC и JtR с номерами и названиями алгоритмов хеширования в Hashcat и John.

Кроме этого, имеется краткое описание применения, например:

  • Summary: Used in Bitcoin Blockchain and Shadow Files.
  • Summary: Used in Wireguard, Zcash, IPFS and more.
  • Summary: Not considered a hash function

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

Для проверки множества хешей используйте опцию -f (—file):

Формат файла — один хеш на строку.

Одна из этих опций (-t или -f) являются обязательной.

Если ваши хеши кодированы в Base64, то используйте опцию -b64 (—base64). Она говорит программе перед идентификацией декодировать хеши из Base64. Для файлов со смешанными строками Base64 и в обычном тексте программа пытается вначале декодировать base64 и если это не получается, то трактует хеш как обычную строку без кодировки.

Обратите внимание, что в качестве хеша (после шапки) показана уже декодированная строка.

Опция -e (—extreme) включает поиск хешей в строке. Этот режим получит 5d41402abc4b2a76b9719d911017c592 из ####5d41402abc4b2a76b9719d911017c592###.

По идее, следующие две команды должны дать одинаковый результат:

Но у меня они получились разные. Поэтому используйте этот режим скорее как экспериментальный.

Бесплатное онлайн определение типа хеша

Сервис Онлайн определение типа хеша существует уже давно. Он работает очень просто — вы вводите хеш и получаете тип хеша. Ранее он основывался на утилитах hashID и HashTag. Теперь сервис обновлён и работает с утилитами HAITI и Name That Hash — самыми актуальными инструментами для определения типа хеша.

Заключение

Как можно убедиться, трудно выбрать, какая из программ лучше — HAITI или Name That Hash. Можно пользоваться или двумя. Либо если вам нужен вывод в формате JSON или вам нужна поддержка API или библиотека для определения хешей, то вы можете выбрать наиболее подходящую для ваших потребностей.

Определения типов хэшей при помощи скрипта hash-Identifier для расшифровки паролей

Когда вы имеете дело с неизвестным хэшем, первый шаг – корректная идентификация типа.

image

Определения типов хэшей при помощи скрипта hash-Identifier для расшифровки паролей

Автор: Kody

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

Помимо взлома хэшей hash-identifier также полезен для идентификации алгоритма, используемого при выдаче контрольной суммы для загрузки файлов. Кроме того, этот скрипт помогает определить, к какому приложению относится хэшированный файл или значение (например, SQL базе или какому-либо другому формату, специфичному для конкретного поставщика).

Что такое хэш и как расшифровать пароль?

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

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

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

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

Читайте так же:
Удалённый доступ с бесплатной программой SupRemo

Например, сможете ли вы на глаз определить, к какому типу относятся хэши, указанные ниже?

Хотя вы могли видеть и тот и другой хэш ранее, ответ на вопрос, какой хэш — MD5, а какой — SHA1, не столь очевиден. Еще большая путаница может возникнуть со схожими типами хэшей, относящиеся к разным режимам в Hashcat. В случае с хэшами, приведенными выше, этот факт имеет чрезвычайно важное значение.

При использовании Hashcat для взлома этого хэша мы должны установить опцию –m с целью работы в нужном режиме. Для взлома хэша MD5 мы бы указали режим 0.

В итоге, установив нужный алгоритм и используя хороший словарь, после расшифровки хэша мы получили слово «hashcat».

Какие хэши поддерживаются?

На данный момент Hashcat в состоянии расшифровать большое количество хэшей. В репозитории на GitHub для утилиты hash-identifier список поддерживаемых хэшей очень внушителен:

Что понадобится

Для начала нужно установить Python3 на вашем компьютере (есть версии для разных платформ). Кроме того, вам понадобится утилита Hashcat, которую можно загрузить, используя команду apt install hashcat, после обновления системы при помощи команд apt update и apt upgrade.

Если вы хотите сгенерировать ваши собственные хэши для тестового взлома, то можете воспользоваться командой в формате echo n PLAINTEXT | (HASHTYPE)sum. Например, при создании хэша SHA1 для слова «nullbyte» я запустил следующую команду:

Шаг 1. Загрузка и установка Hash-Identifier

Установить скрипт, написанный на Python, – очень просто. Откройте терминал и запустите следующую команду:

Затем посмотрите содержимое директории hash-identifier:

Вы должны обнаружить файл hashid.py, который можно запустить при помощи команды ниже:

Шаг 2. Идентификация неизвестных хэшей

В качестве пробного подхода при помощи hash-identifier попробуем опознать следующие пять неизвестных хэшей:

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

Второй хэш, показанный ниже, опознается как SHA256. Другой вероятный вариант — Haval256.

Третий хэш опознается как SHA1:

Четвертый хэш опознается как SHA512:

Наконец, пятый и последний хэш опознается как MD5:

Все прошло без особых проблем. Следующий шаг – поиск нужного режима, соответствующего обнаруженному типу, который будет указываться в Hashcat во время взлома.

Шаг 3. Подбор режима в Hashcat

При поиске нужного режима мы можем взглянуть на огромный список хэшей, поддерживаемых в Hashcat. Сокращенный вариант с наиболее популярными типами приведен ниже:

В списке выше есть два примера, которые могут соответствовать первому хэшу (7196759210defdc0), рассмотренному нами в предыдущем шаге. На первый взгляд, режим 200 «MySQL323» наиболее соответствует. Подтвердить гипотезу можно при помощи проверки тестового хэша в hash-identifier.

Точное совпадение с нужным хэшем:

Если мы попробуем другой тип (300), то увидим, что результаты не совпадают.

Соответственно, еще раз убеждаемся, что режим 200 выбран правильно.

Шаг 4. Расшифровка хэша при помощи Hashcat

После идентификации типа хэша и подбора нужно режима можно приступать к расшифровке пароля в Hashcat. Вначале нужно создать словарь с паролями, который будет использоваться в Hashcat для атаки на хэш. В сети есть много доступных списков, например, RockYou, но в нашем случае мы будем создавать тестовый словарь example.dict с несколькими паролями.

Если вы все еще находитесь внутри скрипта hash-identifier, нажмите CtrlC, а затем откройте файл в текстовом редакторе nano, запустив следующую команду:

После добавления нескольких предполагаемых паролей, один из которых – «hashcat», нажимаем CtrlX для выхода из редактора и вводим Y, чтобы сохранить изменения в файле. Теперь мы можем использовать этот файл в качестве словаря вместе с ранее выбранным режимом для взлома хэша. Базовая команда выглядит примерно так:

Вместо значения HASH_VALUE указываем хэш 7196759210defdc0, вместо MODE_NUMBER – подобранный ранее режим 200. Результат работы показан ниже. Если у вас старая система, как в моем случае – нужно указать параметр force.

В результате мы получили 7196759210defdc0:hashcat и смогли расшифровать хэш посредством сравнения с элементами словаря из файла example.dict.

Когда вы имеете дело с неизвестным хэшем, первый шаг – корректная идентификация типа. Хотя скрипт hash-identifier – не идеален, но позволяет без особых проблем опознать наиболее распространённые хэши и отличить разные типа хэшей, которые выглядят одинаково, но требуют разных режим работы в Hashcat. Даже если hash-identifier не уверен, с каким типом вы имеете дело, сравнение с результатами примеров с сайта Hashcat, может помочь в идентификации.

Надеюсь это руководство, посвященное опознанию неизвестных хэшей, вам понравилось.

Хэширование в строковых задачах

Хэш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.

  • Быстро считается — за линейное от размера объекта время;
  • Имеет не очень большие значения — влезающие в 64 бита;
  • «Детерминированно-случайная» — если хэш может принимать (n) различных значений, то вероятность того, что хэши от двух случайных объектов совпадут, равна примерно (frac<1>) .

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

Для некоторых задач удобнее работать с хэшами, чем с самими объектами. Пусть даны (n) строк длины (m) , и нас просят (q) раз проверять произвольные две на равенство. Вместо наивной проверки за (O(q cdot n cdot m)) , мы можем посчитать хэши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

  • Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
  • Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём (n) изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию (f) с областью значений ([0, n)) . При обработке .insert(x) мы будем добавлять элемент (x) в (f(x)) -тый список. При ответе на .find(x) мы будем проверять, лежит ли (x) -тый элемент в (f(x)) -том списке. Благодаря «равномерности» хэш-функции, после (k) добавлений ожидаемое количество сравнений будет равно (frac) = (O(1)) при правильном выборе (n) .
  • Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
  • Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
  • Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
  • Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди (m) точек в (n) -мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

Хэшируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.

Сегодня же мы остановимся на строках.

Полиномиальное хэширование

Лайфхак: пока вы не выучили все детерминированные строковые алгоритмы, научитесь пользоваться хэшами.

Будем считать, что строка — это последовательность чисел от (1) до (m) (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c — ‘a’ + 1) .

Определим прямой полиномиальный хэш строки как значение следующего многочлена:

[ h_f = (s_0 + s_1 k + s_2 k^2 + ldots + s_n k^n) mod p ]

Здесь (k) — произвольное число больше размера алфавита, а (p) — достаточно большой модуль, вообще говоря, не обязательно простой.

Его можно посчитать за линейное время, поддерживая переменную, равную нужной в данный момент степени (k) :

Можем ещё определить обратный полиномиальный хэш:

[ h_b = (s_0 k^n + s_1 k^ + ldots + s_n) mod p ]

Его преимущество в том, что можно написать на одну строчку кода меньше:

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хэш и обозначать его просто буквой (h) .

Зачем это нужно?

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

Например, если нужно посчитать хэш от конкатенации строк (a) и (b) (т. е. (b) приписали в конец строки (a) ), то можно просто хэш (b) домножить на (k^<|a|>) и сложить с хэшом (a) :

Удалить префикс строки можно так:

А суффикс — ещё проще:

В задачах нам часто понадобится домножать (k) в какой-то степени, поэтому имеет смысл предпосчитать все нужные степени и сохранить в массиве:

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

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

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

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

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за (O(1)) .

Упражнение. Напишите то же самое, но используя обратный полиномиальный хэш — этот способ тоже имеет право на существование, и местами он даже проще. Обратный хэш подстроки принято считать и использовать в стандартном виде из определения, поскольку там нет необходимости в делении.

Лайфхак. Если взять обратный полиномиальный хэш короткой строки на небольшом алфавите с (k=10) , то числовое значение хэша строки будет наглядно соотноситься с самой строкой:

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хэши от всех подстрок за (O(n^2)) и добавим их все в std::set . Чтобы получить ответ, просто вызовем set.size() .

Поиск подстроки в строке. Можно посчитать хэши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хэш текущей подстроки. Если хэш какой-то из этих подстрок совпал с хэшом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение строк (больше-меньше, а не только равенство). У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше сравним два символа, идущие за ним.

Палиндромность подстроки. Можно посчитать два массива — обратные хэши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно.

Хранение строк в декартовом дереве

Если для вас всё вышеперечисленное тривиально: можно делать много клёвых вещей, если «оборачивать» строки в декартово дерево. В вершине дерева можно хранить символ, а также хэш подстроки, соответствующей её поддереву. Чтобы поддерживать хэш, нужно просто добавить в upd() пересчёт хэша от конкатенации трёх строк — левого сына, своего собственного символа и правого сына.

Имея такое дерево, мы можем обрабатывать запросы, связанные с изменением строки: удаление и вставка символа, перемещение и переворот подстрок, а если дерево персистентное — то и копирование подстрок. При запросе хэша подстроки нам, как обычно, нужно просто вырезать нужную подстроку и взять хэш, который будет лежать в вершине-корне.

Если нам не нужно обрабатывать запросы вставки и удаления символов, а, например, только изменения, то можно использовать и дерево отрезков вместо декартова.

Вероятность ошибки и почему это всё вообще работает

У алгоритмов, использующих хэширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хэширование — можно в оффлайне сгенерировать тест против конкретного решения.

Событие, когда два хэша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set (O(n^2)) различных случайных значений в промежутке ([0, m)) . Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать (m) , чтобы не бояться такого?

Выбор констант

Практическое правило: если вам нужно хранить (n) различных хэшей, то безопасный модуль — это число порядка (10 cdot n^2) . Обоснование — см. парадокс дней рождений.

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

Можно также брать модуль (2^<64>) . У него есть несколько преимуществ:

  • Он большой — второй модуль точно не понадобится.
  • С ним ни о каких переполнениях заботиться не нужно — если все хранить в unsigned long long , процессор сам автоматически сделает эти взятия остатков при переполнении.
  • С ним хэширование будет быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию % .

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако, его добавляют далеко не на все контесты — имейте это в виду.

В выборе же (k) ограничения не такие серьезные:

  • Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
  • Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.

Главное — чтобы значения (k) и модуля не знал человек, который генерирует тесты.

Парадокс дней рождений

В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.

Более общее утверждение: в мультимножество нужно добавить (Theta(sqrt)) случайных чисел от 1 до n, чтобы какие-то два совпали.

Первое доказательство (для любителей матана). Пусть (f(n, d)) это вероятность того, что в группе из (n) человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от (1) до (d) .

[ f(n, d) = (1-frac<1>) times (1-frac<2>) times . times (1-frac) ]

Попытаемся оценить (f) :

Из последнего выражения более-менее понятно, что вероятность (frac<1><2>) достигается при (n approx sqrt) и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем (frac<2>) индикаторов — по одному для каждой пары людей ((i, j)) — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна (frac<1>) .

Обозначим за (X) число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть (frac <2>cdot frac<1>) .

Отсюда понятно, что если (d = Theta(n^2)) , то ожидание равно константе, а если (d) асимптотически больше или меньше, то (X) стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа

Алгоритм Рабина-Карпа предназначен для поиска подстроки в строке.

Содержание

Метод хеширования [ править ]

Наивный алгоритм поиска подстроки в строке работает за [math]Oleft(n^2right)[/math] в худшем случае — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом хеширования.

Определение:
Пусть дана строка [math]s[0..n-1][/math] . Тогда полиномиальным хешем (англ. polynomial hash) строки [math]s[/math] называется число [math]h = mathrm(s[0..n-1]) = p^ <0>s[0] + . + p^ s[n-1][/math] , где [math]p[/math] — некоторое простое число, а [math]s[i][/math] [math]<->[/math] код [math]i[/math] -ого символа строки [math]s[/math] .

Проблему переполнения при вычислении хешей довольно больших строк можно решить так [math]<->[/math] считать хеши по модулю [math]r=2^<64>[/math] (или [math]2^<32>[/math] ), чтобы модуль брался автоматически при переполнении типов.

Для работы алгоритма потребуется считать хеш подстроки [math]s[i..j][/math] . Делать это можно следующим образом:

Рассмотрим хеш [math]s[0..j][/math] :

[math]mathrm(s[0..j]) = s[0] + p s[1] +. + p^ s[i-1] + p^ s[i] +. + p^ s[j-1] + p^ s[j][/math]

Разобьем это выражение на две части:

[math]mathrm(s[0..j]) = (s[0] + p s[1] +. + p^ s[i-1]) + (p^ s[i] +. + p^ s[j-1] + p^ s[j])[/math]

Вынесем из последней скобки множитель [math]p^[/math] :

[math]mathrm(s[0..j]) = (s[0] + p s[1] +. + p^ s[i-1]) + p^(s[i] +. + p^ s[j-1] + p^ s[j])[/math]

Выражение в первой скобке есть не что иное, как хеш подстроки [math]s[0..i-1][/math] , а во второй — хеш нужной нам подстроки [math]s[i..j][/math] . Итак, мы получили, что:

Отсюда получается следующая формула для [math]mathrm(s[i..j])[/math] :

Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с [math]i[/math] , нужно предпосчитать все [math]p^[/math] для [math]i in [0..n — 1][/math] . Это займет много памяти. Но поскольку нам нужны только подстроки размером [math]m[/math] [math]<->[/math] мы можем подсчитать хеш подстроки [math]s[0..m-1][/math] , а затем пересчитывать хеши для всех [math]i in [0..n — m][/math] за [math]O(1)[/math] следующим образом:

[math]mathrm(s[i + 1..i + m — 1]) = (mathrm(s[i..i + m — 1]) — p^ s[i]) bmod r[/math] .

[math]mathrm(s[i + 1..i + m]) = (p cdot mathrm(s[i + 1..i + m — 1]) + s[i + m]) bmod r[/math] .

Получается : [math]mathrm(s[i + 1..i + m]) = (p cdot mathrm(s[i..i + m — 1]) — p^ s[i] + s[i + m]) bmod r[/math] .

Решение [ править ]

Алгоритм [ править ]

Алгоритм начинается с подсчета [math]mathrm(s[0..m-1])[/math] и [math]mathrm(p[0..m-1])[/math] , а также с подсчета [math]p^[/math] , для ускорения ответов на запрос.

Для [math]i in [0..n — m][/math] вычисляется [math]mathrm(s[i..i + m — 1])[/math] и сравнивается с [math]mathrm(p[0..m-1])[/math] . Если они оказались равны, то образец [math]p[/math] скорее всего содержится в строке [math]s[/math] начиная с позиции [math]i[/math] , хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.

Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки [math]<->[/math] выгоднее будет предпосчитать все степени [math]p[/math] , а также хеши всех префиксов строки [math]s[/math] .

Псевдокод [ править ]

Приведем пример псевдокода, который находит все вхождения строки [math]w[/math] в строку [math]s[/math] и возвращает массив позиций, откуда начинаются вхождения.

Новый хеш [math]hashS[/math] был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что [math]s[n + 1][/math] — пустой символ.

Время работы [ править ]

Изначальный подсчёт хешей выполняется за [math]O(m)[/math] .

Каждая итерация выполняется за [math]O(1)[/math] , В цикле всего [math]n — m + 1[/math] итераций.

Итоговое время работы алгоритма [math]O(n + m)[/math] .

Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет [math]O(n[/math] [math]cdot[/math] [math]m)[/math] .

голоса
Рейтинг статьи
Ссылка на основную публикацию