Практика «Diff Tool» на языке C#

Практика «Diff Tool»

Алгоритм из предыдущей задачи находит похожие пары документов. В этой задаче вам предстоит проанализировать два документа и найти в них повторяющиеся части. Подобную задачу решают так называемые Diff Tools — инструменты для сравнения текстовых файлов.

Для этого вам нужен алгоритм, который будет по двум последовательностям токенов возвращать их наибольшую общую подпоследовательность. Она должна состоять из токенов первой последовательности, которые в том же порядке присутствуют и во второй последовательности (токены не обязательно должны идти подряд). И из всех таких последовательностей вернуть нужно самую длинную. Если самых длинных несколько, можно вернуть любую.

Например, у документов a1 b2 ab1 b21 b2 и b2 b2 a1 (токены разделены пробелом) наибольшая общая подпоследовательность — это b2 b2 и имеет длину 2 токена.

Реализуйте это в методе Calculate в классе LongestCommonSubsequenceCalculator и отладьте реализацию на тестах LongestCommonSubsequenceCalculator_Tests. Как и в прошлой задаче документы приходят в ваш метод уже разбитые на токены, вам этого делать не нужно.

Более подробное описание задачи находится в приложенном файле.