/*
	We demonstrate the reduction
	of the MCSP problem to the k-Frechet decision problem.

	Given two strings A and B, we ask for a partition
	A = A_1 A_2 ... A_n
	B = B_1 B_2 ... B_n
	such that A_i = B_j for each i and for some j.

	Now, for an instance of MCSP we construct curves P and Q as follows:
	first we subdivide the unit interval into c intervals of equal size,
	where c denotes the number of different letters in both strings. 

	We then identify every letter of the alphabet Σ with a number in {1, . . . , c}.
	Next we transform string A into a curve P and string B into curve Q:
	for every letter l in a string we form a polygonal chain
	consisting of five segments: the first connecting ( 1/2 , 0) to ( 1/2 , l/c ) vertically,
	a second connecting ( 1/2 , l/c ) to (0, l/c ) horizontally, followed by (0, l/c ) to (1, l/c ), 
	back to ( 1/2 , l/c ) and finally back to (1/2, 0). 
	The result is a T -shape.
*/

//var A = "1232"; 
//var B = "3221"; 
var A = "12343214"; 
var B = "21431423"; 

var cmap = [];
var c = 0;

// map letters to indexes
function map_letters(str) 
{
	for(var i=0; i < str.length; ++i)
	{
		var code = str.charCodeAt(i);
		//console.warn(code);
		if (typeof cmap[code] === 'undefined')
			cmap[code] = ++c;
	}
}

map_letters(A);
map_letters(B);

console.warn("c="+c);
console.assert(c!=0, "c must not be zero");

// Start at (1/2,0)
// Note: P and Q are predefined variables (need not be declared)
P.M(0.5,0);
Q.M(0.5,0);

// create T-shapes
function tshape(l, c) {
	var p = new Path();
	var d = l/c;
	p.v(d).h(-0.5).h(+1).h(-0.5).v(-d);
	return p;
}

for(var i=0; i < A.length; ++i)
	P.appendPath(tshape(cmap[A.charCodeAt(i)],c));
for(var i=0; i < B.length; ++i)
	Q.appendPath(tshape(cmap[B.charCodeAt(i)],c));

// scale for better visualisation
P.scale(10*c);
Q.scale(10*c);