Данный репозиторий содержит краткое изложение произведения (А. Бхаргава, "Грокаем алгоритмы"). Содержимое репозитория не содержит лишней информации (на мой взгляд), что значительно помогает в усвоении материала. Помимо краткого изложения, репозиторий содержит анимированные изображения (GIF), программный код на Java/Kotlin. Надеюсь, что материал, представленный в репозитории, будет Вам полезен!
| # | Заголовок | Примеры |
|---|---|---|
| 1 | Знакомство с алгоритмами | Java, Kotlin |
| 2 | Сортировка выбором | Java, Kotlin |
| 3 | Рекурсия | Java, Kotlin |
| 4 | Быстрая сортировка | Java, Kotlin |
| 5 | Хеш-таблицы | Java, Kotlin |
| 6 | Поиск в ширину | Java, Kotlin |
| 7 | Алгоритм Дейкстры | Java, Kotlin |
| 8 | Жадные алгоритмы | Java, Kotlin |
| 9 | Динамическое программирование | Java, Kotlin |
- Бинарный поиск
- Сортировка выбором
- Рекурсия
- Быстрая сортировка
- Хеш-таблицы
- Поиск в ширину
- Алгоритм Дейкстры
- Жадные алгоритмы
- Динамическое программирование
Алгоритмом называется набор инструкций для выполнения некоторой задачи. В принципе, любой фрагмент программного кода можно назвать алгоритмом.
Бинарный поиск - алгоритм; на входе он получает отсортированный список элементов. Если элемент, который необходимо найти, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null.
При бинарном поиске каждый раз исключается половина чисел.
Для списка из n элементов бинарный поиск выполняется за log2(n) шагов, тогда как простой поиск будет выполнен за n шагов.
Например. Для списка из 8 чисел необходимо 3 итерации, поскольку 2^3 = 8. Для списка из 1024 элементов потребуется 10 итераций, так как 2^10 = 1024.
Бинарный поиск работает только в том случае, если список отсортирован.
Реализация алгоритма на Java: Binary Search
Линейное время - время, когда максимальное количество попыток совпадает с размером списка.
Итак, простой поиск выполняется за время O(n), а бинарный поиск - за время O(log n).
Ниже перечислены пять разновидностей "О-большого", которые будут встречаться особенно часто, в порядке убывания скорости выполнения.
Примеры "O-большого"
- O(log n), или логарифмическое время. Пример: бинарный поиск.
- O(n), или линейное время. Пример: простой поиск.
- O(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка).
- O(n^2). Пример: медленные алгоритмы сортировки (сортировка выбором).
- O(n!). Пример: очень медленные алгоритмы (задача о коммивояжере).
- Скорость алгоритмов не измеряется в секундах.
- Время выполнения алгоритма описывается ростом количества операций.
- Время выполнения алгоритмов выражается как "О-большое".
Сортировка выбором (англ. selection sort) - простой алгоритм сортировки, который имеет сложность O(n^2).
На каждом i-ом шаге находим i-ый минимальный элемент и меняем его местами с i-ым элементом в массиве. Таким образом будет получен массив, отсортированный по возрастанию.
Ответ на данный вопрос связан с ролью констант в "О-большом". Да, в действительности не нужно каждый раз проверять список из n элементов. Сначала проверяются n элементов, потом n - 1, n - 2 ... 2, 1. В среднем проверяется список из 1/2 * n элементов. Его время выполнения составит O(n * 1/2 * n). Однако константы (такие как 1/2) в "O-большом" игнорируются, поэтому мы просто используем O(n * n), или O(n^2).
Рекурсия - метод программирования, используемый во многих алгоритмах.
Рекурсия вызывает у людей противоречивые чувства. Они либо обожают её, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее.
Ли Колдуэлл (с сайта Stack Overflow) сказал:
Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!
Каждая рекурсивная функция состоит из двух частей: базового случая и рекурсивного случая. В рекурсивном случае функция вызывает сама себя. В базовом случае функция себя не вызывает, чтобы предотвратить зацикливание.
♦ Рассмотрим следующую задачу. Написать функцию для вывода обратного отсчета.
Посмотреть решение задачи
Все это время, работая с рекурсией, мы пользовались стеком вызовов.
Концепция стека вызовов играет важную роль в программировании вообще; кроме того, ее важно понимать при использовании рекурсии.
Реализация стека вызовов
Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это делается, на примере вычисления факториала.
Вычисление факториала
Стек удобен, но у него есть своя цена: сохранение промежуточной информации может привести к значительным затратам памяти. Каждый вызов функции занимает не много памяти, но если стек станет слишком высоким, это будет означать, что ваш компьютер сохраняет информацию по очень многим вызовам. На этой стадии есть два варианта:
- Переписать код с использованием цикла.
- Попробовать воспользоваться так называемой хвостовой рекурсией.
- Когда функция вызывает саму себя, это называется рекурсией.
- В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный.
- Стек поддерживает две операции: занесение и извлечение элементов.
- Все вызовы функций сохраняются в стеке вызовов.
- Если стек вызовов станет большим, он займет слишком много памяти.
Быстрая сортировка - элегантный алгоритм сортировки, часто применяемый на практике. Алгоритм быстрой сортировки использует стратегию "разделяй и властвуй".
Алгоритм быстрой сортировки работает намного быстрее сортировки выбором. Он является хорошим примером элегантного кода.
Итак, представьте, что вы фермер, владеющий земельным участком. Земельный участок представлен на рисунке ниже.
Вы хотите равномерно разделить землю на одинаковые квадратные участки. Участки должны быть настолько большими, насколько это возможно.
Как определить наибольший размер квадрата для участка? Воспользуйтесь стратегией "разделяй и властвуй"! Алгоритмы на базе этой стратегии являются рекурсивными.
Решение задачи методом "разделяй и властвуй" состоит из двух шагов:
- Сначала определяется базовый случай. Это должен быть простейший случай из всех возможных.
- Задача делится или сокращается до тех пор, пока не будет сведена к базовому случаю.
Для начала разметим самые большие участки, которые можно использовать.
Итак, в исходном наделе можно разместить два участка 640 х 640, и еще останется место. Тут-то и наступает момент истины. Нераспределенный остаток - это тоже надел земли, который нужно разделить. То есть к нему (нераспределенному остатку) необходимо применить тот же алгоритм.
Таким образом, мы только что сократили задачу с размера 1680 х 640 до 640 х 400! Двигаемся дальше!
Теперь нам необходимо разделить сегмент 640 х 400. Размеры самого большого квадрата, который можно создать, составляют 400 х 400 м (см. рисунок ниже).
После разделения остается меньший сегмент с размерами 400 х 240 м. Разделим этот сегмент (см. рисунок ниже).
Отсекая поделенную часть, мы приходим к еще меньшему размеру сегмента, 240 х 160 м.
После очередного отсечения получается еще меньший сегмент (см. рисунок ниже).
Ура, мы пришли к базовому случаю: 160 кратно 80. Если разбить этот сегмент на квадраты, ничего лишнего не останется!
Итак, для исходного надела земли самый большой размер участка будет равен 80 х 80 м.
Алгоритм Евклида
"Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы."Если Вас интересует доказательство, поищите "алгоритм Евклида".
Как работает стратегия "разделяй и властвуй":
- Определите простейший случай как базовый.
- Придумайте, как свести задачу к базовому случаю.
Таким образом, мы рассмотрели суть стратегии "разделяй и властвуй".
В языках функционального программирования, таких как Haskell, циклов нет, поэтому для написания функций приходится применять рекурсию. Если вы хорошо понимаете рекурсию, вам будет проще изучать функциональные языки.
Совет
Когда вы пишете рекурсивную функцию, в которой задействован массив, базовым случаем часто оказывается пустой массив или массив из одного элемента. Если вы не знаете, с чего начать, - начните с этого.
- Имеется массив чисел. Нужно просуммировать все числа и вернуть сумму. Решить задачу, используя рекурсию.
- Написать рекурсивную функцию для подсчета элементов в списке.
- Найдите наибольшее число в списке.
Быстрая сортировка относится к алгоритмам сортировки. Она работает намного быстрее сортировки выбором и часто применяется в реальных программах. Quick sort основана на стратегии "разделяй и властвуй".
Воспользуемся быстрой сортировкой для упорядочения массива.
Итак, что будет являться базовым случаем?
Пустые массивы и массивы, содержащие всего один элемент, станут базовым случаем. Такие массивы можно просто возвращать в исходном виде - сортировать ничего не нужно.
Алгоритм быстрой сортировки работает так: сначала в массиве выбирается элемент, который называется опорным.
Затем определяются элементы, меньшие опорного, и элементы, большие опорного. Этот процесс называется разделением.
Алгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента.
В худшем случае быстрая сортировка работает за время O(n^2). Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время O(n log n).
Вопросы, которые возникают:
- что в данном случае понимается под "худшим" и "средним" случаем?
- если быстрая сортировка в среднем выполняется за время O(n log n), а сортировка слиянием выполняется за время O(n log n) всегда, то почему бы не использовать сортировку слиянием? Разве она не быстрее?
Попробуем выяснить, какая сортировка работает быстрее: сортировка слиянием или быстрая сортировка.
Допустим, у нас имеется простая функция для вывода каждого элемента в списке:
def print_items(list):
for item in list:
print itemЭта функция последовательно перебирает все элементы списка и выводит их. Так как функция перебирает весь список, она выполняется за время O(n).
Изменим нашу функцию (print_items), добавив секундную паузу перед выводом значения:
from time import sleep
def print_items2(list):
for item in list:
sleep(1)
print itemРабота функций продемонстрирована ниже:
# Имеется список из пяти элементов: 2|4|6|8|10
print_items: 246810
print_items2: 2 <пауза> 4 <пауза> 6 <пауза> 8 <пауза> 10 <пауза>Обе функции проходят по списку один раз, и обе выполняются за время O(n).
Вопрос. Какая из них работает быстрее?
Ответ. print_items работает намного быстрее, потому что она НЕ делает паузу перед выводом каждого элемента.
Следовательно, даже при том, что обе функции имеют одинаковую скорость "О-большое", реально print_items работает быстрее.
Стоит понимать, когда мы используем "О-большое" (например, O(n)), в действительности это означает следующее: c * n.
Здесь
c- некоторый фиксированный промежуток времени для алгоритма. Он называется константой. Например, время выполнения может составлять 10 миллисекунд * n для print_items против 1 секунды * n для print_items2.
Обычно константа игнорируется, потому что если два алгоритма имеют разное время "О-большое", она роли не играет.
Для примера возьмем бинарный и простой поиск. Допустим, что константы присутствуют в обоих алгоритмах.
10 мс * n 1 с * log n
__________ ___________
// Простой поиск // Бинарный поискНаша реакция будет следующей: "Ого! У простого поиска константа равна 10 миллисекундам, а у бинарного поиска - 1 секунда. Простой поиск намного быстрее!"
Но, давайте предположим, что поиск ведется по списку из 4 миллиардов элементов, тогда время будет таким:
Простой поиск | 10 мс * 4 миллиарда = 463 дня (c * n, где с = 10 мс).
Бинарный поиск | 1 с * 32 = 32 секунды (с * log n, где с = 1 с). Как можем заметить, бинарный поиск все равно работает намного быстрее. Константа ни на что не повлияла.
Однако в некоторых случаях константа может иметь значение. Один из примеров такого рода - быстрая сортировка и сортировка слиянием. У быстрой сортировки константа меньше, чем у сортировки слиянием, поэтому, несмотря на то что оба алгоритма характеризуются временем O(n log n), быстрая сортировка работает быстрее.
- Стратегия «разделяй и властвуй» основана на разбиении задачи на уменьшающиеся фрагменты. Если вы используете данную стратегию со списком, то базовым случаем, скорее всего, будет являться пустой массив или массив из одного элемента.
- Если вы реализуете алгоритм быстрой сортировки, то в качестве опорного следует выбрать случайный элемент. Среднее время выполнения быстрой сортировки составляет О(n log n)!
- Константы в «О-большом» иногда могут иметь значение. Именно по этой причине быстрая сортировка быстрее сортировки слиянием.
Представьте, что вы являетесь продавцом в маленьком магазинчике. Когда клиент покупает товары, вы проверяете их цену по книге. Если записи в книге не упорядочены по алфавиту, то поиск слова «апельсины» в каждой строке займет слишком много времени. Конечно, если же книга упорядочена по алфавиту, вы можете воспользоваться бинарным поиском, время которого составляет всего O(log n).
Но поиск данных в книге - головная боль, даже если ее содержимое отсортировано. Пока вы листаете страницы, клиент потихоньку начинает выходить из себя. Гораздо удобнее было бы завести помощницу, которая помнит все названия товаров и цены. Тогда ничего искать вообще не придется: вы спрашиваете помощницу, а она мгновенно отвечает.
В данной ситуации отлично подойдет структура данных, которая называется хеш-таблица.
Хеш-функция представляет собой функцию, которая получает строку и возвращает число. Под "строкой" в данном случае следует понимать любые данные.
В научной терминологии говорят, что хеш-функция «отображает строки на числа". Можно подумать, что найти закономерности получения чисел для подаваемых на вход строк невозможно. Однако хеш-функция должна соответствовать некоторым требованиям:
- Она должна быть последовательной. Допустим, вы передали ей строку "апельсины" и получили 4. Это значит, что каждый раз в будущем, передавая ей строку «апельсины», вы будете получать 4. Без этого хеш-таблица бесполезна.
- Разным словам должны соответствовать разные числа. Например, хеш-функция, которая возвращает 1 для каждого полученного слова, никуда не годится. В идеале каждое входное слово должно отображаться на свое число.
Отметим, что хеш-таблицы исключительно быстро работают! Обращение к элементу массива происходит мгновенно, а хеш-таблицы используют массивы для хранения данных, поэтому при обращении к элементам они не уступают массивам.
В любом приличном языке существует реализация хеш-таблиц. Хеш-таблицы также известны под другими названиями: «ассоциативные массивы» , «словари», «отображения», «хеш-карты» или просто «хеши».
Задача. Предположим, вы руководите избирательным участком. Естественно, каждый избиратель может проголосовать всего один раз. Как проверить, что он голосовал ранее? Когда человек приходит голосовать, вы узнаете его полное имя, а затем проверяете по списку уже проголосовавших избирателей. Если имя входит в список, значит, этот человек уже проголосовал - гоните наглеца! В противном случае вы добавляете имя в список и разрешаете ему проголосовать.
Но... Как быть, когда список проголосовавших станет огромным?
Неужели нужно будет каждый раз, когда кто-то приходит голосовать,
просматривать гигантский список и проверять, голосовал он или нет?
Существует эффективное решение: воспользоваться хешем!
Решение задачи на Java:
Решение задачи на Kotlin:
Может случиться так, что у двух разных ключей окажется одинаковый хэш. Или хэш будет разным, но по формуле позиция для обоих хэшей будет одинаковой. Тогда значения обоих ключей окажутся записаны в одну «корзинку». Это и есть коллизия. Именно из-за коллизий для хранения значений используется связанный список: если бы в массиве просто хранился объект, любая коллизия перезаписала бы текущее значение, а это опасно. А при текущей реализации, даже если случится коллизия, новое значение просто запишется в начало той же «корзинки», не изменив старое.
Итак, можно сделать два вывода:
- выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;
- если связанные списки становятся слишком длинными, работа с хеш-таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции!
Коэффициент заполнения хеш-таблицы вычисляется по простой формуле: количество элементов в хеш-таблице / общее количество элементов. Например, в следующей хеш-таблице коэффициент заполнения равен 3/4.
С меньшим коэффициентом загрузки число коллизий уменьшается, и ваша таблица начинает работать более эффективно. Хорошее приближенное правило: изменяйте размер хеш-таблицы, когда коэффициент заполнения превышает 0,7. Но ведь на изменение размеров уходит много времени, скажете вы, и будете абсолютно правы! Да, изменение размеров требует значительных затрат ресурсов, поэтому оно не должно происходить слишком часто. В среднем хеш-таблицы работают за время 0(1) даже с изменением размеров.
Хеш-таблицы чрезвычайно полезны, потому что они обеспечивают высокую скорость операций и позволяют по-разному моделировать данные.
- Хеш-таблица создается объединением хеш-функции с массивом.
- Коллизии нежелательны. Хеш-функция должна свести количество коллизий к минимуму.
- Хеш-таблицы обеспечивают очень быстрое выполнение поиска, вставки и удаления.
- Хеш-таблицы хорошо подходят для моделирования отношений между объектами.
- Как только коэффициент заполнения превышает 0,7, пора изменять размер хеш-таблицы.
- Хеш-таблицы используются для кэширования данных (например, на веб-серверах).
- Хеш-таблицы хорошо подходят для обнаружения дубликатов.
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Например, с помощью поиска в ширину можно:
- написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;
- реализовать проверку правописания (минимальное количество изменений, преобразующих ошибочно написанное слово в правильное, например АЛГОРИФМ -> АЛГОРИТМ - одно изменение);
- найти ближайшего к вам врача.
Алгоритм поиска в ширину (англ. breadth-first search, BFS) позволяет найти кратчайшие пути из одной вершины невзвешенного (ориентированного или неориентированного) графа до всех остальных вершин. Под кратчайшим путем подразумевается путь, содержащий наименьшее число ребер.
Задание. Реализовать граф (на программном уровне), который представлен на рисунке ниже.
Граф состоит из нескольких узлов. И каждый узел соединяется с соседними узлами. Возникает вопрос: какую структуру данных использовать, чтобы реализовать данные отношения?
Будем использовать хеш-таблицу!
Код на языке Java выглядит так:
private static Map<String, List<String>> graph = new HashMap<>();
graph.put("you", Arrays.asList("alice", "bob", "claire"));
graph.put("bob", Arrays.asList("anuj", "peggy"));
graph.put("alice", Arrays.asList("peggy"));
graph.put("claire", Arrays.asList("thom", "jonny"));
// У Ануджа, Пегги, Тома и Джонни соседей нет.
graph.put("anuj", Collections.emptyList());
graph.put("peggy", Collections.emptyList());
graph.put("thom", Collections.emptyList());
graph.put("jonny", Collections.emptyList());В хеш-таблицах элементы не упорядочены, поэтому добавлять пары "ключ-значение" можно в любом порядке.
Анудж является соседом Боба, но Боб не является соседом Ануджа. Такой граф называется направленным - отношения действуют только в одну сторону.
Реализация алгоритма на Java находится в BreadthFirstSearch.java
Если поиск продавца манго был выполнен по всей сети, значит, вы прошли по каждому ребру (напомню: ребром называется соединительная линия или линия со стрелкой, ведущая от одного человека к другому). Таким образом, время выполнения составляет как минимум О(количество ребер).
Также в программе должна храниться очередь поиска. Добавление одного человека в очередь выполняется за постоянное время: О(1). Выполнение операции для каждого человека потребует суммарного времени О(количество людей). Поиск в ширину выполняется за время О(количество людей + количество ребер), что обычно записывается в форме O(V+E) (V - количество вершин, Е - количество ребер).
Алгоритм Дейкстры используется для поиска пути от начальной точки к конечной за кратчайшее возможное время.
Алгоритм Дейкстры состоит из четырех шагов:
- Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).
- Обновить стоимости соседей этого узла.
- Повторять, пока это не будет сделано для всех узлов графа.
- Вычислить итоговый путь.
Когда вы работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом. Граф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом.
В ненаправленном графе каждое новое ребро добавляет еще один цикл. Алгоритм Дейкстры работает только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph).
Хочется отметить, что алгоритм Дейкстры не может использоваться при наличии ребер, имеющих отрицательный вес. Такие ребра нарушают работу алгоритма.
Посмотрим, как алгоритм Дейкстры реализуется в программном коде. Ниже изображен граф, который будет использоваться в этом примере.
Реализация алгоритма на языке Java представлена в DijkstraAlgorithm.java
Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Ответы
А - 8; В - 60; С - каверзный вопрос (кратчайший путь не существует из-за наличия цикла с отрицательным весом).Допустим, имеется учебный класс, в котором нужно провести как можно больше уроков. Вы получаете список уроков (см. рисунок ниже).
Провести в классе все уроки не получится, потому что некоторые из них перекрываются по времени.
Вроде бы сложная задача, верно? На самом деле алгоритм оказывается на удивление простым. Вот как он работает:
- Выбрать урок, завершающийся раньше всех. Это первый урок, который будет проведен в классе.
- Затем выбирается урок, начинающийся после завершения первого урока. И снова следует выбрать урок, который завершается раньше всех остальных. Он становится вторым уроком в расписании.
Продолжайте действовать по тому же принципу - и вы получите ответ!
Таким образом, школьные уроки, которые будут проводиться в классе, отмечены галочкой.
Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других.
В технической терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. Хотите верьте, хотите нет, но этот простой алгоритм успешно находит оптимальное решение задачи составления расписания!
Вы открываете собственную авторскую программу на радио и хотите, чтобы вас слушали во всех 50 штатах. Нужно решить, на каких радиостанциях должна транслироваться ваша передача. Каждая станция стоит денег, поэтому количество станций необходимо свести к минимуму. Имеется список станций. Каждая станция покрывает определенный набор штатов, эти наборы перекрываются.
Как найти минимальный набор станций, который бы покрывал все 50 штатов?
Вот как выглядит жадный алгоритм, который выдает результат, достаточно близкий к оптимуму:
- Выбрать станцию, покрывающую наибольшее количество штатов, еще не входящих в покрытие. Если станция будет покрывать некоторые штаты, уже входящие в покрытие, это нормально.
- Повторять, пока остаются штаты, не входящие в покрытие.
Программный код располагается в директории greedy_algorithms.
Динамическое программирование - метод решения сложных задач, разбиваемых на подзадачи, которые решаются в первую очередь.
Представим, что у нас есть рюкзак, в котором можно унести товары общим весом до 4 фунтов.
Есть три предмета, которые можно уложить в рюкзак.
- Ноутбук, который весит 3 фунта и стоит 2000$;
- Магнитофон — 4 фунта мощи, которые обойдутся в 3000$;
- Гитара — весит 1 фунт, а стоит 1500$.
Какие предметы следует положить в рюкзак, чтобы стоимость добычи была максимальной?
Чтобы решить задачу, воспользуемся приёмами динамического программирования.
Разобьём задачу на подзадачи и будем последовательно их решать. При этом на каждом следующем шаге используем результаты предыдущего.
Решение задачи на Java: задача о рюкзаке
Рассмотрим еще один пример.
Допустим, вы открыли сайт dictionary.com. Пользователь вводит слово, а сайт возвращает определение. Но если пользователь ввел несуществующее слово, нужно предположить, какое слово имелось в виду.
Алекс ищет определение "fish", но он случайно ввел "hish". Такого слова в словаре нет, но зато у вас есть список похожих слов.
СЛОВА, ПОХОЖИЕ НА "НISН":
- FISH
- VISTA
Итак, Алекс ввел строку hish. Какое слово он хотел ввести на самом деле: fish или vista?
Решение задачи представлено в директории longest_common_subsequence