두 배열/문자열 간의 차이점 (추가 및 삭제)을 받으십시오.

Question

사용자 입력 (키보드)에 의해 업데이트되는 array이 있습니다. 더 나은 라이브 퍼포먼스를 얻기 위해 엔트리가 어떻게 변했는지 추적하고 싶습니다. 여기에 예를

:

// ascii values for 'Stuckoverflow' 
var previousBlocks = [ 
    83, 116, 117, 99, 107, 111, 118, 
    101, 114, 102, 108, 111, 119 
]; 

// ascii values for 'Stackedoverflow2014' 
var blocks = [ 
    83, 116, 97, 99, 107, 101, 100, 111, 118, 
    101, 114, 102, 108, 111, 119, 
    50, 48, 49, 52 
]; 

내가 previousBlocks에서 blocks에 추가되거나 제거 된 항목의 위치를 ​​싶어. 더 큰 변경되지 않은 부분은 그대로 유지되어야합니다. (여기서는 "오버 플로우") 판독 인간

var result = { 
    deletions: [2], 
    additions: [2, 5, 6, 13, 14, 15, 16] 
}; 

차이가 다음과 같이 표현 될 수있는 다음 array는 (입력)은 사용자에 의해 조작 도착

St[-u][+a]ck[+e][+d]overflow[+2][+0][+1][+4] 

Answer 1

때문에 변화가 클러스터. 이 솔루션은 하나의 변경 범위를 계산하고 대체 블록을 결정합니다. 그것은 매우 쉬운 해결책이지만 그 일을합니다.

var start = 0; 
var end = 0; 
var length = Math.min(previousBlocks.length, length); 

// compare from left to right 
while (
    start < length 
    && previousBlocks[start] 
     == blocks[start] 
) { 
    start ++; 
} 

// compare from right to left 
while (
    end < length - start 
    && previousBlocks[previousBlocks.length - end - 1] 
     === blocks[blocks.length - end - 1] 
) { 
    end ++; 
} 

// collect the blocks that have been added 
var rangeBlocks = []; 
for (var i = start; i < blocks.length - end; i ++) 
{ 
    rangeBlocks.push(blocks[i]); 
} 

return { 
    // unchanged amount of blocks on the left 
    startOffset: start, 

    // unchanged amount of blocks on the right 
    endOffset: end, 

    // exchange/replace the changed part by these blocks 
    blocks: rangeBlocks 
};