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

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

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

Предисловие

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

Привет. С вами олимпиадное хобби. Здесь мы выбираем себе олимпиадную задачу по программированию, разбираем ее, вырабатываем возможные пути решения и реализовываем задуманное, после чего отправляем на суд. Нам потребуется знание одного из языков программирования: c, c++, java, pascal, терпение, ловкость и базовые знания английского языка, чтобы понимать условие задачи, хотя последний пункт необязателен, ведь я вольно перескажу условие на русском языке.

Вы не забыли размяться? Если забыли, то быстренько разминайтесь, и возвращайтесь к нам.

Напоминаю, что я беру задачи с сайта http://uva.onlinejudge.org, и сегодня случайный выбор пал на задачку под номером 154 — задачу об утилизации отходов.

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

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

Предупреждаю, что статья содержит около 2000 слов (8 страниц А4), но дорогу осилит идущий.

Одним из новшеств Ubuntu 10.10 стал переход с «голой» ALSA на PulseAudio. Ранее постилось много советов прибить и удалить его для решения проблем, однако теперь PulseAudio стабилен, с ним не шипят колонки ;), и он способен на такое, что не снилось Alsa :)

В статье я с самого начала расскажу что это такое и как оно работает, а так же:

• Как переключить весь звук на USB-колонку на закрывая приложений (usb hotplug);
• Как выбрать порт звуковой карты для вывода звука (колонки ноутбука/наушника, LineOut/Наушники);
• Как выбрать профайл звуковой карты (маппинг физических портов: 5.1 или стерео+lineIn?);
• Как управлять громкостью и усиливать тихий сигнал (!);
• Как сделать Skype громче музыки?

И представлю своё решение, призванное упростить управление PulseAudio ;)

Хочу признаться сразу, что я вас отчасти обманул, ибо драйвер, если верить википедии — это компьютерная программа, с помощью которой другая программа (обычно операционная система) получает доступ к аппаратному обеспечению некоторого устройства. А сегодня мы создадим некую заготовку для драйвера, т.к. на самом деле ни с каким железом мы работать не будем. Эту полезную функциональность вы сможете добавить сами, если пожелаете.

То, что мы сегодня создадим, корректнее будет назвать LKM (Linux Kernel Module или загрузочный модуль ядра). Стоит сказать, что драйвер – это одна из разновидностей LKM.

Писать модуль мы будем под ядра линейки 2.6. LKM для 2.6 отличается от 2.4. Я не буду останавливаться на различиях, ибо это не входит в рамки поста.

Мы создадим символьное устройство /dev/test, которое будет обрабатываться нашим модулем. Хочу сразу оговориться, что размещать символьное устройство не обязательно в каталоге /dev, просто это является частью «древнего магического ритуала».

Еще давно очень многих интересовал один вопрос: «Эта программа занимает всего 100 кб, что за музыку она воспроизводит? Как это работает?»

Так вот, называется это чудо – Трекерная музыка. И что самое главное – она занимает очень мало места, в отличие от .mp3 или .wav. В современных популярных ОС трекерные файлы (MOD, XM, S3M, IT и пр.) проигрываются большинством медиаплееров, например, Winamp, VLC, Amarok, Audacious и другими.

Скачать такую музыку можно, например отсюда — keygenmusic.net, или отсюда www.modarchive.org. Это отнюдь не единственные ресурсы, стоит только обратиться к поиску.

Для того, чтобы воспроизвести такую музыку в своей программе, нам потребуется минимальное знание C++, а также minifmod, доступный в исходниках. Как заявляют разработчики, minifmod добавит всего 50 кб к вашему exe-файлу (без учета сжатия).

Введение

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

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Все мы пользуемся динамически-компонуемыми билиотеками. Их возможности поистине великолепны. Во-первых, такая библиотека загружается в физическое адресное пространство только один раз для всех процессов. Во-вторых, можно расширять функционал своей программы, подгружая дополнительную библиотеку, которая и будет этот функционал обеспечивать. И все это без перезапуска самой программы. А еще решается проблема обновлений. Для динамически компонуемой библиотеки можно определить стандартный интерфейс и влиять на функционал и качество своей основной программы, просто меняя версию библиотеки. Такие методы повторного использования кода даже получили название «архитектура plug-in’ов». Но топик не об этом.

Кстати, нетерпеливые могут все скачать и попробовать прямо сейчас.

В свете последних событий с torrents.ru и активизации государственных группировокорганов по борьбе с пиратством, думаю многие задумались как же обезопасить себя или свой сервер на случай если придут нежданные «гости». Вот и мне подвернулась задача защитить локальный медиасервер от посягательств, проведя пару дней за гугленнием и чтением мануалов/howto — мне удалось это реализовать. Скажу сразу, статей по шифрованию очень много, но в основном они рассчитаны на шифрование только определенных разделов, либо устарели/содержат много ошибок.

ЦЕЛИ:

1. Весь винт(винты) должны быть надежно зашифрованы
2. На винтах не должно быть абсолютно никакой разбивки, так как будто это новый(или стертый) винт
3. ОС должна стоять на зашифрованных разделах
4. Должна быть возможность увеличения дискового пространства, путем добавления новых винтов
5. Загрузка системы без ввода ключа от шифрованных данных

Введение
Я только недавно столкнулся с виндовыми доменами (Active Directory) и познаю много нового и удивительного. Так уж получилось, что значительное количество пользователей в домене организации имеют права локальных админов (технические специалисты, программисты и другие) (ведь не редко так бывает?). Но последствия от этого колоссальны. В данной статье мы рассмотрим как можно подслушивать звуки (разговоры, переговоры) на удаленных машинах.

Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.

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

Техника, известная как «Чтение по спирали/по часовой стрелке» (“Clockwise/Spiral Rule”) позволяет любому программисту разобрать любое объявление языка Си.

Следуйте этим простым шагам:

Современный Linux (2.6+) может обнаруживать новоподключенные устройства (на шинах, которые поддерживают hotplug). Их можно, так же отключать, предварительно отмонтировав файловые системы и сделав sync. Среди hotplug шин не только USB, но и SATA, SCSI и SAS (в теории, это же применимо и к PATA, но там много глупых контроллеров, которые не умеют адекватно реагировать на исчезновение устройства).

Отключать их лучше не дёргая на ходу физическое устройство, а сказав ядру полностью забыть про про него (гарантируя тем самым, что никаких операций ввода-вывода с устройством производиться не будет, даже если вспохватившийся кеш). Кроме того, иногда нужно выполнять эмуляцию процедуры plug-unplug без физического дёргания питания/шины данных (что не очень хорошо для железа). Самая типичная ситуация — это отладка скриптов udev.

Удаление устройства

echo 1 >/sys/block/sdX/device/delete

(x — буква устройства, sda, sdb, etc).

Эта команда удаляет указанное устройство. Заметим, это низкоуровневая команда, которая не проверяет кеш и статус примонтированности, так что лучше сначала сказать umount & sync.

К сожалению, я не знаю метода совместить выключение шпинделя диска с его удалением с точки зрения ядра. Шпиндель можно отключить командой scsi-spin, однако, при попытке удалить устройство, оно будет раскручено заново и удалено. А у удалённого устройства уже нельзя ничего останавливать (нет устройства). Так что эта часть проблемы пока не решена.

Добавление устройства

Мы не можем «добавить» устройство, мы можем отдать контроллеру команду «перечитать» список устройств, подключенных к тому или иному порту. Если там найдётся что-то интересное, ядру дадут знать.

echo "- - -" >/sys/class/scsi_host/hostX/scan

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

Обратите внимание, host'ы нумеруются с 0, а не с 1. (а в dmesg ata устройства нумеруются с 1).

Так же осуществляется и сканирование USB-SATA переходников (usb-боксов и внешних винчестеров — они просто фигурируют как ещё один scsi_host).

Если мы говорим про SCSI, то вместо "- — -" можно указать точный номер устройства/шины/LUN'а сканируемого устройства (например, «200 1 2»). SATA, в силу архитектурных особенностей (один target для одного initiator) принимает туда только «0 0 0».

Ещё об удалении… Если вы не знаете буквы устройства, но знаете его физическое место подключения, то удалять можно «прямым текстом», записью «1» в "/sys/bus/scsi/devices/targetX:0:0/X:0:0:0/delete".

Пару месяцев назад Rafal Wojtczuk придумал серьёзный эксплойт, позволяющий получить права суперюзера из непривилегированного процесса, имеющего доступ к X-серверу (то есть, из GUI-приложения, работающего под обычным пользователем). Другими словами, любая GUI-программа (например, читалка PDF-файлов), если она скомпроментирована (например, специально подготовленным PDF-файлом), может пробить все барьеры защиты на пути к полному обладанию компьютером. Не спасает даже песочница SElinux (SElinux «sandbox -X»). И проблема существует много лет — по-видимому, с первых версий ядра 2.6.

Обзор этой уязвимости вышел 17 августа в [2], и я хочу о ней рассказать местами в упрощённой, местами в развёрнутой форме.

Как это работает

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