Поиск подстроки в строке по алгоритму Карпа-Рабина

Когда речь заходит об алгоритмах точного поиска подстроки в строке, то обычно все так или иначе сводится к последовательному сравнению символов. Но есть группа алгоритмов, которые основаны не на сравнении символов, а на сравнении числовых данных - хешей. Одним из таких алгоритмов является алгоритм Карпа-Рабина. Его принцип достаточно простой: вычисляется хеш от строки поиска, затем вычисляется хеш от фрагмента строки, в которой производится поиск. Длина фрагмента равна длине искомой строки. Если хеши равны, то выполняется дополнительное посимвольное сравнение, если не равны, то продвигаемся по строке дальше. Казалось бы, что выигрыша тут никакого быть не может, ведь вместо сравнения вычислительные ресурсы тратятся на хеширование. Однако, как показывает практика, для поиска совпадения это гораздо эффективнее, чем сравнение отдельных символов строк. Вместо O(n*m) операций можно добиться среднего результата O(n+m), где n - длина исходной строки, а m - длина искомой строки. К тому же алгоритм Карпа-Рабина не требует выделения дополнительной памяти для своей работы.

Читать статью целиком »

Алгоритм быстрой сортировки на Ассемблере

Алгоритм быстрой сортировки появился еще на заре компьютерной эпохи в 1960 году. И до сих пор он остается одним из самых быстрых универсальных алгоритмов сортировки массивов. Несмотря на некоторые недостатки в виде наличия рекурсивных вызовов, алгоритм быстрой сортировки очень прост в реализации, не требует выделения дополнительной памяти и даже может быть распараллелен между несколькими подпроцессами.

Читать статью целиком »

Использование системных функций хеширования

Я уже выкладывал на сайте ассемблерные реализации алгоритмов хеширования MD4, MD5 и SHA1. Но в Windows есть уже готовые функции для подсчета не только этих хешей, но и некоторых других. Конечно, делать все самому гораздо приятнее для души и полезнее для мозгов, но почему бы не переложить часть работы на систему? Как говорил один мой хороший товарищ: "У лошади голова большая, вот пусть она и думает".

Читать статью целиком »

Как узнать сетевое имя компьютера и название домена

Маленький сниппет для получения сетевого имени компьютера и названия домена. Но сперва структура, которая нам понадобится для работы.C помощью функции NetWkstaGetInfo можно получить информацию о рабочей станции. Полнота информации зависит от кода запрошенной структуры и уровня доступа пользователя. Самый низкий уровень - 100-й - доступен для всех. 101-й код требует как минимум авторизованного пользователя, выше уже необходим доступ с правами администратора.Обратите внимание, что саму структуру WKSTA_INFO_100 в приложении хранить не надо, она создается автоматически где-то в системе. Вся работа выполняется через указатель на эту структуру.

Читать статью целиком »

Как сделать ProgressBar с надписью

Не перестаю удивляться, почему разработчики Microsoft с самого начала не реализовали "из коробки" очевиднейшие решения. Например, есть хороший и удобный элемент диалоговых окон - Progress Bar. Легко реализовать, удобно управлять, но по какой-то причине нет никаких инструментов, чтобы системными средствами наложить на индикатор прогресса какую-нибудь надпись типа "42% завершено". Градиентный ProgressBar мы уже делали, настала очередь реализовать ProgressBar с надписью.


Использовать стандартный элемент msctls_progress32 не будем, вместо него возьмем элемент EDIT или STATIC, как и в предыдущем примере. Полоса индикатора и надпись реализуется путем рисования прямо на канве элемента диалогового окна, которое выделено под индикатор.

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

Читать статью целиком »