Как отметить различия между двумя строками

Question

Мне нужна функция, которая бы визуально отмечала различия между двумя строками.

Пример 1:

Ввод:

• Переполнение стека
• Стек переполнение

Выход:

• Стек [O] verflow
• Стек [o] verflow [ing]

Пример 2:

Ввод:

• Перезапуск Переполнение
• Стек-Ooooverflow

Выход:

• [Res ] tack [] Overflow
• [S] tack [-] O [ooo] verflow

Я много искал, но я всегда заканчиваю с функциями сравнения файлов. Я хочу визуализировать разницу между строками. Один пример, который я нашел, это https://text-compare.com (это именно то, что мне нужно), но, похоже, он использует код на стороне сервера.

Язык не имеет большого значения, JavaScript, Python, но любые указатели, как подходить к этой проблеме, были бы хорошими.

Я не обязательно ищу реализацию; Я бы предпочел иметь ссылки на какой-нибудь сайт, так как это не элементарная проблема. Не слишком сложно, но вы хотите, чтобы все было правильно.

Answer 1

Эту проблему можно решить, найдя самую длинную общую подпоследовательность (LCS) из двух строк, а затем заключив квадратные скобки вокруг тех частей, которые не являются частью LCS.

Например, LCS Stack Overflow и Stack ooverflowing равен Stack verflow, поэтому первая строка будет отображаться как Stack [O]verflow, а вторая как Stack [oo]verflow[ing], потому что это те части, которых нет в LCS.

Существует стандартный алгоритм программирования Dynami c для вычисления LCS, который описан в Википедии, и различные оптимизации для этого алгоритма, которые ускоряют его в практических случаях , Части каждой строки, которых нет в LCS, можно найти с помощью простого l oop, поддерживающего текущий индекс в строке, и другого индекса для текущей позиции в LCS.