Skip to content

Instantly share code, notes, and snippets.

@shimondoodkin
Created February 1, 2013 15:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shimondoodkin/4692150 to your computer and use it in GitHub Desktop.
Save shimondoodkin/4692150 to your computer and use it in GitHub Desktop.
this awesome piece of JavaScript is written by me, by rewriting merge-strings function to use array elements instead of chars. licence: 2 close bsd/public domain
///////////////////////////merge arrays////// wrote by Shimon Doodkin/////////
/*
test mergin two arrays with common merging points
merge
[1,10:55] ,
[2,10:55] ,
[3,10:55]
[2,10:55] ,
[3,10:55] ,
[4,10:55] ,
[5,10:55]
to
[1,10:55] ,
[2,10:55] ,
[3,10:55] ,
[4,10:55] ,
[5,10:55]
*/
function arrays_equal(a,b)
{
if( (!(a instanceof Array))
|| (!(b instanceof Array))
|| a.length != b.length ) return false;
for(var i=0;i<a.length;i++)
{
if((a[i] instanceof Date)&&(b[i] instanceof Date))
{
if(a[i].getTime() !== b[i].getTime()) return false;
}
else if((a[i] instanceof Array)&&(b[i] instanceof Array))
{
if(!arrays_equal(a[i],b[i])) return false;
}
else if(a[i] !== b[i]) return false;
}
return true;
}
// search comparing arrays,
// a JS implementation of Knuth–Morris–Pratt algorithm,
// changed to deep compare arrays
function arrkmp_search(s, w) {
var m = 0, i = 0,
pos, cnd, t,
slen = s.length,
wlen = w.length;
// String to array conversion
//s = s.split("");
//w = w.split("");
// Construct the lookup table
t = [-1, 0];
for ( pos = 2, cnd = 0; pos < wlen; ) {
if ( arrays_equal(w[pos-1], w[cnd]) ) {
t[pos] = cnd + 1;
pos++; cnd++;
}
else if ( cnd > 0 )
cnd = t[cnd];
else
t[pos++] = 0;
}
// Perform the search
while ( m + i < slen ) {
if ( arrays_equal(s[m+i] , w[i]) ) {
i++;
if ( i === wlen )
return m;
}
else {
m += i - t[i];
if ( t[i] > -1 )
i = t[i];
else
i = 0;
}
}
return -1;
}
/*
function merge_arrays(myString01,myString02)
{
//var myString02 = "TwoString";
//var myString01 = "StringOne";
// var myString02 =
//[
//[3,"10:55"] ,
//[4,"10:55"] ,
//[5,"10:55"]
//];
// var myString01 =
//[
//[1,"10:55"] ,
//[2,"10:55"] ,
//[3,"10:55"]
//]
// var myString01 = "StringOne";
// var myString02 = "StringTwo";
// var myString01 = "OneString";
// var myString02 = "TwoString";
// var myString01 = "OneString";
// var myString02 = "StringTwo";
// console.log("First String is = " , myString01);
// console.log("Second String is = " , myString02);
var commonString = [];
for (var i = 0; i < myString01.length; i++) {
if (arrkmp_search(myString02,myString01.slice(i)) >= 0) {
commonString = myString01.slice(i);
break;
}
}
if (commonString.length==0) {
for (var i = 0; i < myString02.length; i++) {
if (arrkmp_search(myString01,myString02.slice(i)) >= 0) {
commonString = myString02.slice(i);
break;
}
}
}
var firstPart;
if (arrkmp_search(myString01,commonString) > 0) {
firstPart = myString01.slice(0, arrkmp_search(myString01,commonString));
} else {
firstPart = myString01.slice(arrkmp_search(myString01,commonString) + commonString.length);
}
var secondPart;
if (arrkmp_search(myString02,commonString) > 0) {
secondPart = myString02.slice(0, arrkmp_search(myString02,commonString));
} else {
secondPart = myString02.slice(arrkmp_search(myString02,commonString) + commonString.length);
}
if (commonString.length==0)
{
firstPart=myString01
secondPart=myString02
}
//console.log("First Part = " , firstPart);
//console.log("Second Part = " , secondPart);
//console.log("Common Part = " , commonString);
var finalString = firstPart.concat(commonString,secondPart);
//var finalString = firstPart.concat(commonString,secondPart);
//console.log("Final String of " , myString01 , " and " , myString02 , " is " , finalString);
return finalString
}
exports.merge_arrays=merge_arrays;
*/
function merge_arrays(myString01,myString02)
{
//var myString02 = "TwoString";
//var myString01 = "StringOne";
/*
var myString02 =
[
[3,"10:55"] ,
[4,"10:55"] ,
[5,"10:55"]
];
var myString01 =
[
[1,"10:55"] ,
[2,"10:55"] ,
[3,"10:55"]
]*/
// var myString01 = "StringOne";
// var myString02 = "StringTwo";
// var myString01 = "OneString";
// var myString02 = "TwoString";
// var myString01 = "OneString";
// var myString02 = "StringTwo";
// console.log("First String is = " , myString01);
// console.log("Second String is = " , myString02);
var commonString = [];
for (var i = 0; i < myString01.length; i++) {
if (arrkmp_search(myString02,myString01.slice(i)) >= 0) {
commonString = myString01.slice(i);
break;
}
}
if (commonString.length==0) {
for (var i = 0; i < myString02.length; i++) {
if (arrkmp_search(myString01,myString02.slice(i)) >= 0) {
commonString = myString02.slice(i);
break;
}
}
}
var firstPart;
if (arrkmp_search(myString01,commonString) > 0) {
firstPart = myString01.slice(0, arrkmp_search(myString01,commonString));
} else {
firstPart = myString01.slice(arrkmp_search(myString01,commonString) + commonString.length);
}
var secondPart;
if (arrkmp_search(myString02,commonString) > 0) {
secondPart = myString02.slice(0, arrkmp_search(myString02,commonString));
} else {
secondPart = myString02.slice(arrkmp_search(myString02,commonString) + commonString.length);
}
if (commonString.length==0)
{
firstPart=myString01
secondPart=myString02
}
//console.log("First Part = " , firstPart);
//console.log("Second Part = " , secondPart);
//console.log("Common Part = " , commonString);
var finalString = firstPart.concat(commonString,secondPart);
//var finalString = firstPart.concat(commonString,secondPart);
//console.log("Final String of " , myString01 , " and " , myString02 , " is " , finalString);
return {first:firstPart,common:commonString,second:secondPart,full:finalString};
}
exports.merge_arrays=merge_arrays;
//example:
/*
console.log(merge_arrays(
[
[1,"10:55"] ,
[2,"10:55"] ,
[3,"10:55"]
],[
[3,"10:55"] ,
[4,"10:55"] ,
[5,"10:55"]
]))
*/
/*
merge strings as an example for merge arrays
String myString01 = "StringOne";
String myString02 = "TwoString";
// String myString01 = "StringOne";
// String myString02 = "StringTwo";
// String myString01 = "OneString";
// String myString02 = "TwoString";
// String myString01 = "OneString";
// String myString02 = "StringTwo";
console.log("First String is = " + myString01);
console.log("Second String is = " + myString02);
String commonString = "";
for (var i = 0; i < myString01.length; i++) {
if (myString02.indexOf(myString01.substring(i)) >= 0) {
commonString = myString01.substring(i);
break;
}
}
if (commonString=="") {
for (int i = 0; i < myString02.length(); i++) {
if (myString01.indexOf(myString02.substring(i)) >= 0) {
commonString = myString02.substring(i);
break;
}
}
}
String firstPart;
if (myString01.indexOf(commonString) > 0) {
firstPart = myString01.substring(0, myString01.indexOf(commonString));
} else {
firstPart = myString01.substring(myString01.indexOf(commonString) + commonString.length());
}
String secondPart;
if (myString02.indexOf(commonString) > 0) {
secondPart = myString02.substring(0, myString02.indexOf(commonString));
} else {
secondPart = myString02.substring(myString02.indexOf(commonString) + commonString.length());
}
System.out.println("First Part = " + firstPart);
System.out.println("Second Part = " + secondPart);
System.out.println("Common Part = " + commonString);
String finalString = firstPart + commonString + secondPart;
System.out.println("Final String of " + myString01 + " & " + myString02 + " is " + finalString);
function arrays_equal(c,d)
{
var a = c, b = d,flg = 0;
if( (!(a instanceof Array))
|| (!(b instanceof Array))
|| a.length != b.length ) return false;
for(var i=0;i<a.length;i++)
if(a[i] !== b[i]) return false;
return true;
}
function kmp_search(s, w) {
var m = 0, i = 0,
pos, cnd, t,
slen = s.length,
wlen = w.length;
// String to array conversion
s = s.split("");
w = w.split("");
// Construct the lookup table
t = [-1, 0];
for ( pos = 2, cnd = 0; pos < wlen; ) {
if ( w[pos-1] === w[cnd] ) {
t[pos] = cnd + 1;
pos++; cnd++;
}
else if ( cnd > 0 )
cnd = t[cnd];
else
t[pos++] = 0;
}
// Perform the search
while ( m + i < slen ) {
if ( s[m+i] === w[i] ) {
i++;
if ( i === wlen )
return m;
}
else {
m += i - t[i];
if ( t[i] > -1 )
i = t[i];
else
i = 0;
}
}
return -1;
}
*/
///////////////////////////end merge///////////////
console.log(merge_arrays(
[
[1,"10:55"] ,
[2,"10:55"] ,
[3,"10:55"]
],[
[3,"10:55"] ,
[4,"10:55"] ,
[5,"10:55"]
]).second);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment