How do you implement the " Command+P" function?

As a programer, you may probably use ⌘+P a lot to search your file, conveniently, you don't have to enter the full path,it can also get the result you want, see the example below:

The blue highlight text is your input, it's not a complete path but the editor still get you the correct file, so, here is the question: how do we implement the ⌘+P function?

LCS

The key is Longest Common Subsequence,for example:

Input: str1 = "abcdef", str2 = "bcfg"
Output: "bcf"
Explanation: "a", "ac", "bcd", "bcf"...are the subsequence of "abcdef", "bcfg" also have some subsequences, the longest common subsequence is "bcf"

Solution:
Continuing with the example above, S(a, b) means the LCS of a and b and we need to get S("abcdef", "bcfg").

Step1:
The last char of strings is not equal, so
S("abcdef", "bcfg") = Max(S("abcdef", "bcf"), S("abcde", "bcfg"))

Step2: let S("abcdef", "bcf") as our target
The last char of strings is equal, so
S("abcdef", "bcf") = S("abcde", "bc") + 1

Repeat step1 and step2, we can get the answer, here is the code:

function getLCS(str1, str2) { 
    let record = Array.from({ length: str1.length }, () => { 
        return Array.from({ length: str2.length });
    });

    function find(index1, index2) { 
        if (index1 < 0 || index2 < 0) return { len: 0, match: [] };
        if (record[index1][index2] !== undefined) return record[index1][index2];

        let ans = record[index1][index2] = {
            len: 0, 
            match: [],
        }
        if (str1[index1] === str2[index2]) {
            ans.len = 1;
            ans.match.push([index1, index2]);

            let chAns = find(index1 - 1, index2 - 1);
            ans.len += chAns.len;
            ans.match.push(...chAns.match);
        } else { 
            let chAns1 = find(index1 - 1, index2);
            let chAns2 = find(index1, index2 - 1);
            ans = record[index1][index2] = chAns1.len > chAns2.len ? chAns1 : chAns2;
        }

        return ans;
    }

    let ans = find(str1.length - 1, str2.length - 1);
    ans.match.reverse();
    let len = ans.len;
    let str = "";
    for (let i = 0, l = ans.match.length; i < l; i++) { 
        str += str1[ans.match[i][0]]
    };

    return {
        length: len,
        str: str,
        detail: ans
    }
} 

⌘+P

If we get the whole path of all files, and the target is your input, for example:

let filePaths = [
"vue2/vue-2.6/src/core/observer/array.js",
"vue2/vue-2.6/src/core/observer/dep.js",
"vue2/vue-2.6/src/core/observer/index.js",
// ...
];

let target = "vue/src/ob/arr";

each item of filePaths get the LCS with target,we may get results:

let res = filePaths.map(path => getLCS(target, path).str);
console.log(res); // ['vue/src/ob/arr', 'vue/src/o/rr', 'vue/src/o/rr']

but that's not enough, the matched char should be highlighted, so let's add the highlight code:

function highlightRes(target, matchs) {
    if (!matchs.length) return target;

    let ans = "";
    let lastIndex = -1;
    for (let i = 0; i < matchs.length; i++) {
        let charIndex = matchs[i][0];
        let highlightChar = `<span style="color: red;">${target[charIndex]}</span>`;
        ans += (target.slice(lastIndex + 1, charIndex) + highlightChar);
        lastIndex = charIndex;
    }
    if (lastIndex !== target.length - 1) {
        ans += target.slice(lastIndex + 1, target.length);
    }

    return ans;
}

Demo

let filePaths = [
    "vue2/vue-2.6/src/core/observer/array.js",
    "vue2/vue-2.6/src/core/observer/dep.js",
    "vue2/vue-2.6/src/core/observer/index.js",
    // ...
];

let target = "vue/src/ob/arr";

let ipt = document.createElement("input");
let container = document.createElement("div");
document.body.innerHTML = ``;
document.body.appendChild(ipt);
document.body.appendChild(container)
ipt.addEventListener("input", (e) => {
    let content = e.target.value;
    if (!content) {
        container.innerHTML = ``;
        return;
    };

    let res = filePaths.map(path => {
        return highlightRes(path, getLCS(path, content).detail.match)
    });
    container.innerHTML = `
    <div>
        <h3>Search value: ${content}</h3>
        <h3>FilePaths: </h3>
        <div>
            ${filePaths.map(item => {
                return `<div>${item}</div>`
            }).join("")}
        </div>

        <h3>Search result: </h3>
        <div>
            ${res.map(item => {
                return `<div>${item}</div>`
            }).join("")}
        </div>
    </div`
});

The end

There are still some places that can be optimized in this program,for example:

• How should we sort the results by continuity of characters? Continuous result is better than decentralized
• How can we make the search faster?

Hope you can resolve these issues or share some of your own thoughts😊.