How to replace only first sequential occurences (fuzzymatch)?

Question

I'm trying to write "fuzzy" match and I can't find a way to solve this problem:

Data in: makrusakkk, query: mrk, expected result: <b>m</b>ak<b>r</b>usa<b>k</b>kk.

RegExp: "makrusakkk".match(/(m).*?(r).*?(k)/i) returns ["makrusak", "m", "r", "k"].

So the question is: is there a way to get the expected result using RegExp?

Answer 1

I think using regular expression for such problem makes things just more complicated. The following string and loop based solution would lead to the result:

function fuzzySearch(query, input) {
    var inds = patternMatches(query, input);
    if(!inds) return input;

    var result = input;
    for(var i = inds.length - 1; i >= 0; i--) {
        var index = inds[i];
        result = result.substr(0,index) + 
            "<b>" + result[index] + "</b>" + 
            result.substr(index+1);
    }

    return result;
}

function patternMatches(query, input) {
    if(query.length <= 0) {
        return [];
    } else if(query.length == 1) {
        if(input[0] == query[0]) return [0];
        else return [];
    } else {
        if(input[0] != query[0])
        return false;

        var inds = [0];
        for(var i = 1; i < query.length; i++) {
            var foundInd = input.indexOf(query[i], inds[i-1]);
            if(foundInd < 0) {
                return [];
            } else {
                inds.push(foundInd);
            }
        }
        return inds;        
    }
}

var input = "makrusakkksd";
var query = "mrk";
console.log(fuzzySearch(query, input));
console.log(patternMatches(query, input));

Here's a live demo too: http://jsfiddle.net/sinairv/T2MF4/