Добрый день! Подскажите, пожалуйста алгоритм. Пишу небольшую утилиту типа diff.

Дано: две строки.
Например
'svalebra' - строка ДО изменений
'olarlabvalekakara' - строка ПОСЛЕ изменений

Находим максимальную общую подпоследовательность. Она будет такой:
valera

А теперь вопрос: как мне показать, какой символ в новой строке добавился, а какой символ из старой строки удалился?

У меня есть индексы для каждой строки, по которым лежит подпоследовательность.

для старой строки
[ 1, 2, 3, 4, 6, 7 ]
для новой строки
[ 7, 8, 9, 10, 15, 16 ]

Прошу Вашей помощи!)

Выделить цветом... не?

Akina, думаю всё сложнее. Человеку нужен алгоритм, как найти эти символы.

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

Просто предположил. Странно, что в ветке про алгоритмы такая тема находится. Тем более, что решение это 

Я умею находить наибольшую общую последовательность, я это написал.

Суть в том, что удалилась, а что добавилось.
'svalebra' - строка ДО изменений
'olarlabvalekakara' - строка ПОСЛЕ изменений
s-
o+
или s изменилось на o?
b-
larlab+
или larla+?

kaka+

в общем, вопрос в том, как теперь найти изменения, если нашли измененную часть.

RTFM:

Расстояние Левенштейна
Редакционное Предписание

Я правильно понимаю, что я должен посчитать макс. подпоследовательность

'svalebra' до
'olarlabvalekakara' после
получить valera

удалить её из строк, получить
sb
olarlabkaka
и для этого построить редакционное предписание?

или я должен построить редакционное предписание для исходных строк

получить что-то вроде такого
rrmrrmrmiiiiiiiiiii
svalebra
olarlabvalekakara

убрать подпоследовательность не сдвигая элементы и получить то, что надо?

Это сообщение отредактировал(а) dixoNICH - 28.2.2014, 20:18

Немного не получается найти diff, всё же.
http://pastie.org/8815415 - тут код

Расстояние Левенштейна находит правильно, но вот проблемы с восстановлением предписания.

Для строк 

Работает вот так

var FIRST = 'Belko'
var SECOND = 'He234aapap'


{ e: 'REPLACE', s2: undefined, s1: undefined }
{ e: 'REPLACE', s2: 'p', s1: 'o' }
{ e: 'REPLACE', s2: 'a', s1: 'k' }
{ e: 'ERASE', s2: 'p', s1: 'l' }
{ e: 'ERASE', s2: 'a', s1: 'l' }
{ e: 'ERASE', s2: 'a', s1: 'l' }
{ e: 'ERASE', s2: '4', s1: 'l' }
{ e: 'ERASE', s2: '3', s1: 'l' }
{ e: 'EQUALS', s2: '2', s1: 'l' }
{ e: 'REPLACE', s2: 'e', s1: 'e' }

Не могу найти ошибку. Помогите, пожалуйста. Код написан на JS, но, специфических конструкций не используется, так что думал не сложно будет