A bad string difference algo.

some_kind_of_diff.js

var diff = function(beforeStr, afterStr) {
  var i,j,prefixLen=0;
	var before = beforeStr ? beforeStr.split(/ /) : [];
	var after = afterStr ? afterStr.split(/ /) : [];
	var arr = [];
	for (i=0, j=0; i<before.length && j<after.length; i++, j++) {
		if (before[i] === after[j]) {
			prefixLen++;
		} else {
			if (prefixLen) {
				arr.push({cmd: 'skip', arg: prefixLen});
			}
			prefixLen = 0;
			var i_ = i, j_ = j;
			while (j<after.length && before[i] !== after[j]) {
				j++;
			}
			if (j === after.length) {
				while (i_<before.length && before[i_] !== after[j_]) {
					i_++;
				}
			}
			if (j < after.length && before[i] === after[j]) {
				arr.push({cmd: 'add', arg: after.slice(j_, j)});
				prefixLen++;
			} else if (i_ < before.length && before[i_] === after[j_]) {
				arr.push({cmd: 'del', arg: before.slice(i, i_)});
				j = j_;
				i = i_;
				prefixLen++;
			} else {
				arr.push({cmd: 'del', arg: before.slice(i, i_)});
				arr.push({cmd: 'add', arg: after.slice(j_, j)});
				i = i_;
				if (i_<before.length && j<after.length && before[i_] === after[j]) {
					prefixLen++;
				}
			}
		}
	}
	if (j === after.length) {
		if (i !== before.length) {
			if (prefixLen) {
				arr.push({cmd: 'skip', arg: prefixLen});
			}
			arr.push({cmd: 'del', arg: before.slice(i)});
		}
	} else if (i === before.length) {
		if (prefixLen) {
			arr.push({cmd: 'skip', arg: prefixLen});
		}
		arr.push({cmd: 'add', arg: after.slice(j)});
	}
	return arr;
};

var patch = function(beforeStr, diff) {
	var i,j,prefixLen=0;
	var before = beforeStr ? beforeStr.split(/ /) : [];
	var after = [];
	for (var i=0,j=0; i<diff.length; i++) {
		var c = diff[i];
		switch(c.cmd) {
			case 'skip':
				after.push.apply(after, before.slice(j, j+c.arg));
				j += c.arg;
				break;
			case 'add':
				after.push.apply(after, c.arg);
				break;
			case 'del':
				if (before.slice(j, j+c.arg.length).join(" ") === c.arg.join(" ")) {
					j += c.arg.length;
				}
				break;
		}
	}
	after.push.apply(after, before.slice(j));
	return after.join(" ");
};


var Random = {

  byte: function() { return (Math.random()*256) | 0; },

	uint: function(max) {
		return ((Math.random()*(max || (1<<31))) | 0);
	},

	int: function(max) {
		max = max || (1<<31);
		return (Math.random()*max - max/2) | 0;
	},

	length: function(maxLen) {
		maxLen = maxLen || 100;
		var r = Math.random();
		if (r < 0.05) {
			return 0;
		} else if (r > 0.95) {
			return maxLen;
		}
		return (maxLen * Math.random()) | 0;
	},

	char: function() {
		var idx = (Math.random()*40) | 0;
		if (idx >= 26) {
			return 32;
		} else {
			return 65 + idx;
		}
	},

	string: function(maxLen) { 
		var len = Random.length(maxLen);
		var str = '';
		for (var i=0; i<len; i++) {
			str += String.fromCharCode(Random.char());
		}
		return str;
	},

	array: function(gen, maxLen) {
		var len = Random.length(maxLen);
		var a = [];
		for (var i=0; i<len; i++) {
			a.push(gen());
		}
		return a;
	}
};

var eq = function(a,b) {
	if (a != b && !(typeof a === 'number' && typeof b === 'number' && isNaN(a) && isNaN(b))) {
		if (typeof a === typeof b && typeof a === 'object') {
			if (JSON.stringify(a) !== JSON.stringify(b)) {
				var msg = Array.prototype.slice.call(arguments, 2).join(" ");
				throw(Error(msg + " : " + JSON.stringify(a) + " != " + JSON.stringify(b)));
			}
		} else {
			var msg = Array.prototype.slice.call(arguments, 2).join(" ");
			throw(Error(msg + " : " +a + " != " + b));
		}
	}
};


var testDiff = function () {
	for (var i=0; i<10000; i++) {
		var before = Random.string(16);
		var after = Random.string(16);
		eq(patch(before, diff(before, after)), after);
	}
};