function ed_init() {
	global $a;
	global $s1;
	$a[0] = array();
	for($i = 0; $i <= strlen($s1); $i++) {
		$a[0][$i] = $i;
	}
}

function ed_compute($j) {
	global $a;
	global $s1;
	global $s2;
	global $theta;
	$a[$j] = array();
	$a[$j][0] = $j;
	$cutoff = 1000000;
	for($i = 1; $i <= strlen($s1); $i++) {
		if($s1[$i - 1] == $s2[$j - 1]) {
			$a[$j][$i] = $a[$j - 1][$i - 1];
		} elseif($i > 1 && $j > 1 && $s1[$i - 2] == $s2[$j - 1] && $s1[$i - 1] == $s2[$j - 2]) {
			$a[$j][$i] = 1 + min($a[$j - 2][$i - 2], $a[$j][$i - 1], $a[$j - 1][$i]);
		} else {
			$a[$j][$i] = 1 + min($a[$j - 1][$i - 1], $a[$j][$i - 1], $a[$j - 1][$i]);
		}
		if($i >= $j - $theta && $i <= $j + $theta) {
			$cutoff = min($cutoff, $a[$j][$i]);
		}
	}
	return $cutoff;
}


// FSA

function next_edge($state, $arc) {
	if($state == 1 && $arc == "")
		return array(2, "a");
	if($state == 1 && $arc == "a")
		return array(4, "b");
	if($state == 2 && $arc == "")
		return array(3, "b");
	if($state == 4 && $arc == "")
		return array(5, "a");
	if($state == 3 && $arc == "")
		return array(1, "a");
	if($state == 5 && $arc == "")
		return array(1, "b");
	return array();
}
function is_final($state) {
	return ($state == 1);
}

//////////

// THIS IS ALGO 2 (slide 18)

//////////////



$a = array();
$s1 = "abba";
$s2 = "";
$theta = 2;
$alphabet = array("a", "b");

ed_init();
$stack = array();
array_push($stack, array("", "", 1));
while(count($stack)) {
	$pop = array_pop($stack);
	$arr = next_edge($pop[2], $pop[1]);
	if(count($arr)) {
		array_push($stack, array($pop[0], $arr[1], $pop[2]));
		$s2 = $pop[0] . $arr[1];
		if(ed_compute(strlen($s2)) <= $theta) {
			array_push($stack, array($s2, "", $arr[0]));
			if(is_final($arr[0]) && $a[strlen($s2)][strlen($s1)] <= $theta)
				echo "$s2 " . $a[strlen($s2)][strlen($s1)] . "\n";

		}
	}
}
/*
ed_init();
for($i = 1; $i <= strlen($s2); $i++) {
	echo ed_compute($i) . "\n";
}




foreach($a as $t1) {
	foreach($t1 as $t2) {
		echo $t2 . "\t";
	}
	echo "\n";
}
 */