/*
	Implement Regular Expression matching algorithm

	*  - match any 0 or more characters
	.  - match any 1 character

	Examples:
	1) Pattern - ab*cf , Input - ab bbbbcfddcf  (o/p: true), Input - abcf (o/p - true)
	2) Pattern - ab.c , Input - abc (o/p - false), Input - abdc (o/p - true)
*/

function rexMatch($par, $sar){

	// Finished and matched
	if (empty($par) && empty($sar)){
		return true;
	}

	if (!empty($par) && $par[0] == "*" && empty($sar)){
		if (count($par)>1){
			return false; // there are more chars after *
		}else {
			return true;// * is last char
		}
	}

	// If they are not empty BOTH(check previous IF) then return false
	if (empty($par) || empty($sar)){
		return false;
	}

	// In case of "." or match just continue with the next one
	if ($par[0] == "." || $par[0]==$sar[0]){
		return rexMatch(array_slice($par, 1), array_slice($sar, 1));
	}

	// 0 chars, so continue with the next char of pattern and the current char of input
	// OR
	// more chars, so continue with the next char of input and the current of pattern
	if ($par[0] == "*"){
		return (rexMatch(array_slice($par, 1), $sar) || rexMatch($par, array_slice($sar, 1)));
	}

	return false;
}

function isMatch($pattern, $input){
	$par = str_split(trim($pattern));
	$sar = str_split(trim($input));
	return rexMatch($par, $sar);
}

$test = array(
	array("*aabc","abc"), //TRUE
	array("abc*","abc"), //TRUE
	array("ab*cf" , "abbbbbcfddcf"), //TRUE
	array("ab*cf" , "abcf"), //TRUE
	array("ab*cf" , "abf"), //false
	array("ab.c", "abc"), //false
	array("ab.c", "abdc"), //TRUE
	array("*a.b**cd" , "abbscsdcdlldopcdcd"), //TRUE
	);

foreach ($test as $t) {
	$r = isMatch($t[0], $t[1]) ? "TRUE" : "false";
	print "pattern: ".$t[0]." - input: ".$t[1]." ->".$r." \n";
}