Отбор КИС МФТИ (письменный этап) 🎯

ФИО: Цой Максим Вячеславович
Задача: №4 / Системное программирование

How to run 🏃

pip install -r requirements.txt
python3 main.py dir1 dir2 33

• dir1, dir2 - абсолютные или относительные пути к директориям
• Процент сходства передается в виде целого числа от 0 до 100
• (Опционально) Флаг -l для использования расстояния Левенштейна

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

Description 📝

Для решения задачи используется алгоритм Майерса сравнения двух текстов средствами библиотеки google/diff-match-patch.

Программа перебирает пары файлов из двух директорий, делает дополнительные проверки на то, следует ли запускать алгоритм Майерса на них (возможно, один из них слишком маленький, чтобы достичь требуемого процента сходства), затем считывает содержимое файлов и сравнивает их.

Сложность алгоритма Майерса: O(ND), где N, D - длины файлов. Сложность выполнения программы: O(M^2 kl), где M - максимальный размер файлов, k, l - количество файлов в директориях.

Counting similarities 📈

Процент схожести можно считать следующим образом:

• (По умолчанию) Отношение суммарной длины совпадающих частей файлов к максимальной длине обоих файлов
• Отношение расстояния Левенштейна к размеру наибольшего файла. Для такого подсчета используйте флаг -l:

python3 main.py -l dir1 dir2 33