• Поиск подстроки. Алгоритм Кнута–Морриса-Пратта

    В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

    index = -1
    for i in xrange(len(haystack)-len(needle)+1):
        success = True
        for j in xrange(len(needle)):
            if needle[j]<>haystack[i+j]:
                success = False
                break
        if success:
            index = i
            break
    print index
    


    Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

    Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.
    Читать дальше →
  • Файл, который нужно закоммитить перед уходом с работы

    Немножко пятничного настроения в субботу. Я думаю, все видели этот код:

    image

    Но Aras Pranckevičius пошел еще дальше. Как написать код, который не так просто обнаружить?
    И если вначале идут простые примеры, то дальше начинается…
    Осторожно, чистое зло
  • DisLocker. Или находим общий язык с BitLocker в Linux Mint

    DisLocker. Или как найти общий язык с BitLocker в Linux Mint
    Первый вопрос, который может возникнуть у читателя, прочитавшего заголовок: «А зачем?». Ведь в Linux Mint можно преспокойно обойтись без проприетарного BitLocker. К тому же главные достоинства этой технологии, к коим можно отнести простоту использования и создания зашифрованных разделов, а также поддержку «из коробки» во всех последних ОС от Microsoft, проявляются лишь в операционных системах из Редмонда. Кроме того, свободного ПО с подобным, или даже кое в чем превосходящим BitLocker функционалом, в nix-системах достаточно — например, TrueCrypt.

    Во многом я разделяю эту точку зрения, но, бывают случаи, когда BitLocker необходим, а ОС – Linux Mint.
    Читать дальше →
    • +4
    • 15,9k
    • 2
  • Графы для самых маленьких: DFS

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

      Читать дальше →
    • Графы для самых маленьких: Dijkstra или как я не ходил на собеседование в Twitter

        Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.
        В этой статье я постараюсь рассказать алгоритм Дейкстры на примере решения этой задачи в несколько усложненном виде. Всех, кому интересно, прошу под кат.
        Читать дальше →
      • Графы для самых маленьких: BFS

          В предыдущем посте рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
          В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.
          Читать дальше →
          • +17
          • 62,5k
          • 2