Skip to content

Instantly share code, notes, and snippets.

@maettig

maettig/LICENSE.txt

Forked from 140bytes/LICENSE.txt
Created January 18, 2012 19:06
Show Gist options
  • Save maettig/1634957 to your computer and use it in GitHub Desktop.
Save maettig/1634957 to your computer and use it in GitHub Desktop.
Download ZIP
findDiffBetweenStrings in 140byt.es
Raw
README.md

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.

Raw
annotated.js
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
}
Raw
index.js
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]}
Raw
LICENSE.txt
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.
Raw
package.json
{
"name": "findDiffBetweenStrings",
"description": "Simple diff algorithm to compare and highlight the changes in two versions of the same string.",
"keywords": [
"compare",
"diff",
"highlighting",
"string"
]
}
Raw
test.html
<!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>
@dciccale
Copy link

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
Copy link

tsaniel commented Jan 29, 2012

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

@dciccale
Copy link

yeap you're right (: ouch

@williammalo
Copy link

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
Copy link
Author

maettig commented Apr 12, 2012

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

@Kequc
Copy link

Kequc commented May 18, 2016 •
edited
Loading

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