Нахождение разницы между строками в Javascript

Я просмотрел ваш код, и ваша логика для сопоставления строк имеет для меня смысл. Он регистрирует ChangeStart, NewChangeEnd и OldChangeEnd правильно, и алгоритм работает нормально. Вам просто нужно знать, имела ли место вставка, удаление или замена. Вот как бы я поступил.

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

Я приведу вам пример. Рассмотрим следующие строки:

 var NewText = "Hello Worllolds!";
 var OldText = "Hello Worlds!";

 ChangeStart -> 10 //Makes sense
 OldChangeEnd -> 8
 NewChangeEnd -> 11

 console.log("Change: " + NewText.substring(ChangeStart, NewChangeEnd + 1)); 
 //Ouputs "lo"

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

 Comparing end: 
  1(N: 12 O: 12: ! -> !) 
  2(N: 11 O: 11: s -> s) 
  3(N: 10 O: 10: d -> d)  -> You need to stop here!

 //Although there is not a mismatch, but we have reached ChangeStart and 
 //we have already established that characters from 0 -> ChangeStart-1 match
 //That is why it outputs "lo" instead of "lol"

Предполагая, что то, что я только что сказал, имеет смысл, вам просто нужно изменить свои циклы for следующим образом:

 if (NewText.length > OldText.length) {
 for (var i = 1; i < NewText.length && ((OldText.length-i)>=ChangeStart); i++) {
  ...

    NewChangeEnd = NewText.length - i -1;
    OldChangeEnd = OldText.length - i -1;
  if(//Mismatch condition reached){
         //break..That code is fine.
    }
 }

Это условие -> (OldText.length-i)>=ChangeStart заботится об аномалии, о которой я упоминал, и поэтому цикл for автоматически завершается, если это условие достигнуто. Однако, как я уже упоминал, могут быть ситуации, когда это условие достигается до того, как возникает несоответствие, как я только что продемонстрировал. Поэтому вам нужно обновить значения NewChangeEnd и OldChangeEnd на 1 меньше совпадающего значения. В случае несоответствия вы сохраняете значения соответствующим образом.

Вместо else -if мы могли бы просто обернуть эти два условия в ситуации, когда мы знаем, что NewText.length > OldText.length определенно не верно, то есть это либо замена, либо удаление. сильный>. Опять же, NewText.length > OldText.length также означает, что это может быть замена или вставка в соответствии с вашими примерами, что имеет смысл. Таким образом, else может быть чем-то вроде:

else {
for (var i = 1; i < OldText.length && ((OldText.length-i)>=ChangeStart); i++) { 

    ...
    NewChangeEnd = NewText.length - i -1;
    OldChangeEnd = OldText.length - i -1;
  if(//Mismatch condition reached){
         //break..That code is fine.
    }
 }

Если вы уже поняли незначительные изменения, определить конкретные случаи очень просто:

1. Удаление – Условие > ChangeStart > NewChangeEnd. Удалена строка из ChangeStart -> OldChangeEnd.

Удаленный текст -> OldText.substring(ChangeStart, OldChangeEnd + 1);

2. Вставка — Условие -> ChangeStart > OldChangeEnd. Вставлена ​​строка в ChangeStart.

Вставленный текст -> NewText.substring(ChangeStart, NewChangeEnd + 1);

3. Замена. Если NewText != OldText и два вышеуказанных условия не соблюдены, то это является заменой.

Текст в старой строке, которая была заменена -> OldText.substring(ChangeStart, OldChangeEnd + 1);

Текст замены -> NewText.substring(ChangeStart, NewChangeEnd + 1);

Начальная и конечная позиции в OldText, которые были заменены -> ChangeStart -> OldChangeEnd

Я создал jsfiddle, включив в ваш код изменения, которые я упомянул. Возможно, вы захотите проверить это. Надеюсь, это поможет вам начать в правильном направлении.

У меня была аналогичная проблема, и я решил ее следующим образом:

function diff(oldText, newText) {

  // Find the index at which the change began
  var s = 0;
  while(s < oldText.length && s < newText.length && oldText[s] == newText[s]) {
    s++;
  }

  // Find the index at which the change ended (relative to the end of the string)
  var e = 0;
  while(e < oldText.length &&
        e < newText.length &&
        oldText.length - e > s &&
        newText.length - e > s &&
        oldText[oldText.length - 1 - e] == newText[newText.length - 1 - e]) {
    e++;
  }

  // The change end of the new string (ne) and old string (oe)
  var ne = newText.length - e;
  var oe = oldText.length - e;

  // The number of chars removed and added
  var removed = oe - s;
  var added = ne - s;

  var type;
  switch(true) {
    case removed == 0 && added > 0:  // It's an 'add' if none were removed and at least 1 added
      type = 'add';
      break;
    case removed > 0 && added == 0:  // It's a 'remove' if none were added and at least one removed
      type = 'remove';
      break;
    case removed > 0 && added > 0:   // It's a replace if there were both added and removed characters
      type = 'replace';
      break;
    default:
      type = 'none';                 // Otherwise there was no change
      s = 0;
  }

  return { type: type, start: s, removed: removed, added: added };
}

Обратите внимание, что это не решило мою настоящую проблему. Моя проблема заключалась в том, что у меня был редактор с абзацами, каждый из которых моделировался с текстом и коллекцией разметки, определенной с помощью начального и конечного индекса, например. жирным шрифтом от char 1 до char 5. Я использовал это для обнаружения изменений в строке, чтобы я мог соответствующим образом сместить индексы разметки. Но рассмотрим строку:

хххххххх

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

В конце концов я применил совершенно другой подход — я просто проанализировал HTML, созданный редактором, и использовал его для определения начального и конечного индексов разметки.

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

function compareText(oldText, newText)
{
    var difStart,difEndOld,difEndNew;

    //from left to right - look up the first index where characters are different
    for(let i=0;i<oldText.length;i++)
    {
        if(oldText.charAt(i) !== newText.charAt(i))
        {
            difStart = i;
            break;
        }
    }

    //from right to left - look up the first index where characters are different
    //first calc the last indices for both strings
    var oldMax = oldText.length - 1;
    var newMax = newText.length - 1;
    for(let i=0;i<oldText.length;i++)
    {
        if(oldText.charAt(oldMax-i) !== newText.charAt(newMax-i))
        {
            //with different string lengths, the index will differ for the old and the new text
            difEndOld = oldMax-i;
            difEndNew = newMax-i;
            break;
        }
    }

    var removed = oldText.substr(difStart,difEndOld-difStart+1);
    var added = newText.substr(difStart,difEndNew-difStart+1);

    return [difStart,added,removed];
}