Цитата(dixoNICH @ 27.2.2014, 23:05  ) |
| как мне показать, какой символ в новой строке добавился, а какой символ из старой строки удалился? |
Выделить цветом... не?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Diff. Помощь с алгоритмом. |
| Автор: dixoNICH 27.2.2014, 22:05 |
| Добрый день! Подскажите, пожалуйста алгоритм. Пишу небольшую утилиту типа diff. Дано: две строки. Например 'svalebra' - строка ДО изменений 'olarlabvalekakara' - строка ПОСЛЕ изменений Находим максимальную общую подпоследовательность. Она будет такой: valera А теперь вопрос: как мне показать, какой символ в новой строке добавился, а какой символ из старой строки удалился? У меня есть индексы для каждой строки, по которым лежит подпоследовательность. для старой строки [ 1, 2, 3, 4, 6, 7 ] для новой строки [ 7, 8, 9, 10, 15, 16 ] Прошу Вашей помощи!) |
| Автор: Akina 28.2.2014, 09:22 | ||
Выделить цветом... не? |
| Автор: Агрох 28.2.2014, 10:26 |
| Akina, думаю всё сложнее. Человеку нужен алгоритм, как найти эти символы. |
| Автор: Akina 28.2.2014, 10:38 |
| Агрох, судя по тексту, нахождение проблемы не составляет (стандартный алгоритм поиска наибольшей общей подстроки, фигня...). Также, судя по всему, ему нужно чистое совпадение подстроки и показ отличий, а не редакционное предписание. |
| Автор: Агрох 28.2.2014, 12:00 | ||
Просто предположил. Странно, что в ветке про алгоритмы такая тема находится. Тем более, что решение это
|
| Автор: dixoNICH 28.2.2014, 12:30 |
| Я умею находить наибольшую общую последовательность, я это написал. Суть в том, что удалилась, а что добавилось. 'svalebra' - строка ДО изменений 'olarlabvalekakara' - строка ПОСЛЕ изменений s- o+ или s изменилось на o? b- larlab+ или larla+? kaka+ в общем, вопрос в том, как теперь найти изменения, если нашли измененную часть. |
| Автор: Akina 28.2.2014, 12:42 |
| RTFM: Расстояние Левенштейна Редакционное Предписание |
| Автор: dixoNICH 28.2.2014, 20:14 |
| Я правильно понимаю, что я должен посчитать макс. подпоследовательность 'svalebra' до 'olarlabvalekakara' после получить valera удалить её из строк, получить sb olarlabkaka и для этого построить редакционное предписание? или я должен построить редакционное предписание для исходных строк получить что-то вроде такого rrmrrmrmiiiiiiiiiii svalebra olarlabvalekakara убрать подпоследовательность не сдвигая элементы и получить то, что надо? |
| Автор: dixoNICH 1.3.2014, 22:36 |
| Немного не получается найти 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, но, специфических конструкций не используется, так что думал не сложно будет |