//JavaScript implementation by David Brown
//after Sara Baase,<em>Computer Algorithms: Introduction to Design and Analysis</em> 
//(Addison-Wesley Series in Computer Science), 1988. ISBN 0201060353.

//in JavaScript, to access an individual character of a string, use <string>.charAt(<index>)
//strings are zero-indexed, but so are arrays. We can't really ignore the first character of
//our pattern like we could the first location of an array, so we'll just add one when generating
//our output.
// We will need to modify range checks here and there to use zero-indexing.


function KMPsetup(p) //p is the pattern as a string
{
var k, r;
var fail = new Array(p.length);
fail[0]=-1;
for (k = 1; k < p.length; k++) {
r = fail[k-1];
while ( (r>=0) && (p.charAt(r) != p.charAt(k-1)) ) {
	r = fail[r];
	}
fail[k] = r+1
}// for k
return fail;
}//fun KMPsetup

function BMcharJump(p)
{
	//using string property names for charJump object
	//to simulate a sparse array whose properties are 
	//enumerable.
	
	var ch, k;
	var charJump = new Object();
	
	//remember, p is zero-indexed; let's keep k according to Baase's code
	for (k = 1; k <= p.length ; k++) {
		charJump["c"+p.charCodeAt(k-1)]=p.length-k;
	}//for characters in pattern
	return charJump;
}

function BMmatchJump(p)
{
	//if I got the conversion from 1-index to 0-index right 
	//the first time, I'll be surprised.
	//no; I hit some sort of endless loop.
	//Let's try using a 1-index instead for the array; 
	//we copy the code bounds directly and just subtract
	//1 from the index to every charAt call.
	
	var k, q, qq;
	var matchJump = new Array(p.length+1);
	var m = p.length;
	var backup = new Array(m);//back is a reservedish word
	for (k = 1; k <= m ; k++) 
	{
		matchJump[k] = 2*m-k;
	}
	k = m ; q = m+1 ;
	while (k > 0) 
	{
		backup[k] = q;
		while (q <= m && p.charAt(k-1) != p.charAt(q-1) )
		{
			matchJump[q] = Math.min(matchJump[q],m-k);
			q = backup[q];
		}
		k--; q--;
	}//while k>=0
	for (k = 1; k <= q; k++) 
	{
		matchJump[k] = Math.min(matchJump[k],m+q-k);
	}
	qq = backup[q];
	
	while(q <= m) 
	{
		while (q <= qq) 
		{
			matchJump[q] = Math.min(matchJump[q],qq-q+m);
			q++;
		}//while q < qq
		qq = backup[qq];
	} //while q < m
	
	//interestingly, this algorithm fails to set matchJump[m]=1
	//when the pattern consists of a single character, e.g., "aaaa"
	//(Or, I goofed; but it's the only discrepancy I can find.)
	//
	//Baase writes, "(For the righmost pattern position,
	//matchJump is assigned 1. This value is not particularly important;
	//charJump will generally be larger.)"
	//
	//In our class, we declared that it would always be 1 by definition, so:
	matchJump[m]=1;
	
	return matchJump;
}


function doit(p)
{
	outputFailTable(p,KMPsetup(p));
	outputCharJump(p,BMcharJump(p));
	outputMatchJump(p,BMmatchJump(p));
}

function outputCharJump(p,charJump)
{
	var i;
	var o="<table><tr><th>char</th><th>charJump[char]</th></tr>";
	for (char in charJump)
	{
		o += "<tr><td>"+(String.fromCharCode(char.substr(1)))+"</td><td>" + charJump[char] + "</td></tr>";
	}
	o += "<tr><td><em>others</em></td><td>"+p.length+"</td></tr>";
	o += "</table>";
	document.getElementById('charJump').innerHTML=o;
}
function outputFailTable(p,fail)
{
	//fail is 0-indexed; p is 0-indexed
	var i;
	var o="<table><tr><th>k</th><th>p[k]</th><th>fail[k]</th></tr>";
	for (i=0; i < p.length; i++)
	{
		o += "<tr><td>"+(i+1)+"</td><td>" + p.charAt(i) + "</td><td>" + (fail[i]+1) + "</td></tr>";
	}
	o += "</table>";
	document.getElementById('failTable').innerHTML=o;
}
function outputMatchJump(p,matchJump)
{
//	matchJump is 1-indexed, but p is still 0-indexed
	var i;
	var o="<table><tr><th>k</th><th>p[k]</th><th>matchJump[k]</th></tr>";
	for (i=0; i < p.length; i++)
	{
		o += "<tr><td>"+(i+1)+"</td><td>" + p.charAt(i) + "</td><td>" + (matchJump[i+1]) + "</td></tr>";
	}
	o += "</table>";
	document.getElementById('matchJump').innerHTML=o;
}