Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
findDiffBetweenStrings in 140byt.es

I once wrote this diff toolset in PHP to compare edited database records. The algorithm is very simple and fast and works best with short values, e.g. from a database table with many fields. The core function compares two strings (for example two fields from two versions of an edited database record) and returns three numbers, indicating the position and length of the two substrings that are different in both strings. If only a single character was changed, this particular character is highlighted. If a line contains multiple changes, everything from the first to the last different character is highlighted.

Click here to see it in action.

Please note that it does not work in Internet Explorer 9 or below. Replace some [] with .charAt() to fix this.

function(a, b) //compare these two strings
{
for (var c = 0, //start from the first character
d = a.length, e = b.length; //and from the last characters of both strings
a[c] && //if not at the end of the string and
a[c] == b[c]; //if both strings are equal at this position
c++); //go forward
for (; d > c & e > c & //stop at the position found by the first loop
a[d - 1] == b[e - 1]; //if both strings are equal at this position
d--) e--; //go backward
return[c, d - c, e - c] //return position and lengths of the two substrings found
}
function(a,b){for(var c=0,d=a.length,e=b.length;a[c]&&a[c]==b[c];c++);for(;d>c&e>c&a[d-1]==b[e-1];d--)e--;return[c,d-c,e-c]}
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2012 Thiemo Mättig <http://maettig.com>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
{
"name": "findDiffBetweenStrings",
"description": "Simple diff algorithm to compare and highlight the changes in two versions of the same string.",
"keywords": [
"compare",
"diff",
"highlighting",
"string"
]
}
<!DOCTYPE html>
<style type="text/css">
* { border-collapse: collapse; font-family: sans-serif; }
th, td { border-bottom: 1px solid #BBB; padding: .5em; }
.changed { background: #FFD; }
.changed * + * { background: #EFE; }
strong { background: #FEE; border: 1px solid #FBB; border-radius: 2px; color: #E00; }
</style>
<table>
<tr><th>Old version</th><th>Current version</th></tr>
<tr>
<td>This is a simple diff algorithm.</td>
<td>This is a tiny diff algorithm.</td>
</tr>
<tr>
<td>It's 140 bytes only.</td>
<td>It's 126 bytes only.</td>
</tr>
<tr>
<td>It's made for database records to find the location and length of a single change per field.</td>
<td>It's made for database records to find the position and length of a single change per field.</td>
</tr>
<tr>
<td>It works bets with short values since it can't separate multiple changes.</td>
<td>It works best with short values since it can't seperate multiple changes.</td>
</tr>
<tr>
<td>It should not highlight lines that did not changed.</td>
<td>It should not highlight lines that did not changed.</td>
</tr>
<tr>
<td>It should not fail in confusing confusing cases.</td>
<td>It should not fail in confusing cases.</td>
</tr>
</table>
<script type="text/javascript">
var diff =
{
// 124 bytes
findDiffBetweenStrings: function(a, b) //compare these two strings
{
for (var c = 0, //start from the first character
d = a.length, e = b.length; //and from the last characters of both strings
a[c] && //if not at the end of the string and
a[c] == b[c]; //if both strings are equal at this position
c++); //go forward
for (; d > c & e > c & //stop at the position found by the first loop
a[d - 1] == b[e - 1]; //if both strings are equal at this position
d--) e--; //go backward
return[c, d - c, e - c] //return position and lengths of the two substrings found
},
highlightDiff: function(a, b, c) //element, position and length of the substring found
{
if (c) //skip if nothing was found
with (document)
{
var d = createElement('STRONG');
d.appendChild(createTextNode(a.data.substr(b, c)));
with (a.parentNode)
appendChild(d),
appendChild(createTextNode(a.data.slice(b + c))),
parentNode.className = 'changed';
a.data = a.data.slice(0, b);
}
},
highlight: function(a) //requires a table element
{
a = a.getElementsByTagName('TR');
for (var b = a.length; b--; ) //iterate all rows in the table
{
var c = a[b].getElementsByTagName('TD');
if (c[1])
{
var d = c[0].firstChild, e = c[1].firstChild;
c = this.findDiffBetweenStrings(d.data, e.data);
this.highlightDiff(d, c[0], c[1]);
this.highlightDiff(e, c[0], c[2]);
}
}
}
}
diff.highlight(document.getElementsByTagName('TABLE')[0]);
</script>
@tsaniel

This comment has been minimized.

Copy link

commented Jan 19, 2012

Save 1 byte.

function(a,b){for(var c=0,d=a.length,e=b.length;a[c]&&a[c]==b[c];c++);for(;d>c&&e>c&&a[d-1]==b[e-1];d--)e--;return[c,d-c,e-c]}
@maettig

This comment has been minimized.

Copy link
Owner Author

commented Jan 19, 2012

Another "save 1 byte" comment by @tsaniel. :-) Thanks a lot.

@dciccale

This comment has been minimized.

Copy link

commented Jan 29, 2012

cool!
what is below this line is wrong:
you could save 2 bytes using a plceholder for the 'c' variable inside the for loop

function(a,b,c){for(c=0,d=a.length,e=b.length;a[c]&&a[c]==b[c];c++);for(;d>c&&e>c&&a[d-1]==b[e-1];d--)e--;return[c,d-c,e-c]}
@tsaniel

This comment has been minimized.

Copy link

commented Jan 29, 2012

Nope, that would make d and e leak into global scope.

@dciccale

This comment has been minimized.

Copy link

commented Jan 29, 2012

yeap you're right (: ouch

@williammalo

This comment has been minimized.

Copy link

commented Apr 11, 2012

save 2 bytes:

function(a,b){for(var c=0,d=a.length,e=b.length;a[c]&&a[c]==b[c];c++);for(;d>c&e>c&a[d-1]==b[e-1];d--)e--;return[c,d-c,e-c]}
@maettig

This comment has been minimized.

Copy link
Owner Author

commented Apr 12, 2012

Replacing two && with &? Good idea, thank you. Updated.

@Kequc

This comment has been minimized.

Copy link

commented May 18, 2016

For me using while loops was easier to read.

function findDiffBetweenStrings (aa, bb)
{
  let a = aa.length;
  let b = bb.length;
  let c = 0;
  while (aa[c] && aa[c] == bb[c]) { c++; }
  while (a > c && b > c && aa[a - 1] == bb[b - 1]) { a--; b--; }
  return [c, a - c, b - c];
}

I love the simplicity of this solution by the way.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.