Simple string matching algorithm: * for matching any number(>= 0) of characters; ? for matching one random character;

simple-string-matching.html

<script>
    function match(input, rule, matched){
  	if(input.length == 0 && rule.length != 0){
			return '';
		}
		if(rule.length == 0){
			return matched;
		}
		var c1 = rule[0];
		var c2 = input[0];
		
		if(c1 == '?'){
			var result = match(input.substring(1), rule.substring(1), matched? matched + c2: c2);
			if(result == ''){
				// next char match failed, then move on
				return match(input.substring(1), rule, matched);
			}else{
				return result;
			}
		}
		
		if(c1 == '*'){
			//find next none * char
			var i = 1;
			var next_c = null;
			while(i < rule.length){
				if(rule[i] != '*'){
					next_c = rule[i]
					break;
				}
				i++;
			}
			
			if(next_c == null){
				// there's no more rule
				debugger;
				var matched_str =  matched? matched + input: input;
				return matched_str;
			}else{
				// there's more rule
				var rule_left = rule.substring(i);
				// going to search from tail
				// calculate tail positions
				var input_left_start = input.length - rule_left.length;
				var input_left = input.substring(input_left_start);
				var matched_str =  matched? matched + input.substring(0, input_left_start): input.substring(0, input_left_start);
				var result = match(input_left, rule_left, matched_str);
				if(result == ''){
					// match from tail failed, then match from the one before last tail
					while(input_left_start> 0){
						input_left_start--;
						input_left = input.substring(input_left_start);
						matched_str =  matched? matched + input.substring(0, input_left_start): input.substring(0, input_left_start);
						result = match(input_left, rule_left, matched_str);
						if(result == ''){
							continue;
						}else{
							return result;
						}
					}
					// no match found after matching all available tail
					return '';
				}else{
					return result;
				}
			}
		}
		
		if(c1 != c2){
			if(match == undefined){
				// if it's first char in rule, then move on to find it
				return match(input.substring(1), rule, matched);
			}else{
				// if it's not not first char in rule, then step back
				return '';
			}
		}else{
			var result = match(input.substring(1), rule.substring(1), matched? matched + c2: c2);
			if(result == ''){
				// next char match failed, then move on
				return match(input.substring(1), rule, matched);
			}else{
				return result;
			}
		}
    }
	console.log(match('abbbbbbbbbbbbbcdefg', 'a*b*'));
</script>