Пусть дана строка s длины n. Тогда Z-функция ("зет-функция") от этой строки — это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.

Иными словами, z[i] — это наибольший общий префикс строки s и её i-го суффикса.

Примечание.…

Дана окружность (координатами своего центра и радиусом) и прямая (своим уравнением). Требуется найти точки их пересечения (одна, две, либо ни одной).

Вместо формального решения системы двух уравнений подойдём к задаче с геометрической…

Даны N отрезков на прямой, т.е. каждый отрезок задаётся парой координат (X1, X2). Рассмотрим объединение этих отрезков и найдём его длину.

Алгоритм был предложен Кли (Klee) в 1977 году. Алгоритм работает за O (N log N). Было доказано, что этот алгоритм является быстрейшим (асимптотически).

Описание…

Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется найти их пересечение: оно может быть пустым (если отрезки не пересекаются), может быть одной точкой, и может быть целым отрезком (если отрезки накладываются друг на друга).

Работать с отрезками будем как с прямыми: построим…

Дан неориентированный граф G с n вершинами и m рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.

Для…

Даны два числа: n и k. Требуется посчитать, с какой степенью делитель k входит в число n!, т.е. найти наибольшее x такое, что n! делится на k^x.

Рассмотрим сначала случай, когда k простое.

Выпишем выражение для факториала в явном виде:

?? n! =…

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

Решим эту задачу с помощью поиска_в_глубину за O(M).

Произведём серию поисков в…

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

Поиск в глубину
Это один из основных алгоритмов на графах.

В результате поиска в глубину находится лексикографически первый путь в графе.

Алгоритм работает за O(N+M).

Данный код позволяет вызывать функции из сторонних библиотек.

Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.

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

Алгоритм работает за O (n+m), где n — число вершин, m — число рёбер.

Описание…

Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.

Решето Сундарама — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа n. Разработан индийским студентом Сундарамом в 1934 году.

Очередь (читается как Кью, а не Куэуэ) — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO).

Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в n-ую степень за O(log n) умножений (вместо n умножений при обычном подходе).

Более того, описываемый здесь приём применим к любой ассоциативной операции, а не только к умножению чисел. Напомним, операция называется…

Краткий алгоритм по замене адреса импортируемой функции в таблице импорта.

Функция Эйлера phi (n) — это количество чисел от 1 до n, взаимно простых с n. Иными словами, это количество таких чисел в отрезке [1; n], наибольший общий делитель которых с n равен единице.

Данный проект предназначет для публикаций всевозможных алгоритмов на любом из языков программирования (предпочтение отдается C++ / C# / Java / Javascript / Python)

Алгоритмы окружают нас повсюду. По их принципам существует животный мир, люди,…