用字典树来实现前缀匹配

qiufuxing 1月前 286

import console; 

class Trie {
    ctor() {
        this.root = {};
    }
    
    insert = function(word) {
        var node = this.root;
        for(i=1;#word;1){
            var ch = word[i];
            if(!node[ch]){
                node[ch] = {};
            }
            node = node[ch];
        }
        node.isEnd = true;
    }
    
    search = function(word) {
        var node = this.findNode(word);
        return node !== null && node.isEnd === true;
    }
    
    startsWith = function(prefix) {
        return this.findNode(prefix) !== null;
    }
    
    findNode = function(word) {
        var node = this.root;
        for(i=1;#word;1){
            var ch = word[i];
            if(!node[ch]){
                return null;
            }
            node = node[ch];
        }
        return node;
    }
    
    findMatchingWords = function(prefix) {
        var result = {};
        var node = this.findNode(prefix);
        if(node !== null) {
            this.dfs(node, prefix, result);
        }
        return result;
    }
    
    dfs = function(node, currentWord, result) {
        if(node.isEnd) {
            ..table.push(result, currentWord);
        }
        for(ch, nextNode in node) {
            if(type(nextNode) == "table") {
                // 使用 string.fromCharCode 来正确处理字符
                this.dfs(nextNode, currentWord ++ ..string.fromCharCode(ch), result);
            }
        }
    }
}
// 创建LaTeX命令和环境的列表
var latexCommands = {
    // 数学符号
    "\\alpha", "\\beta", "\\gamma", "\\delta", "\\epsilon", "\\zeta", "\\eta", "\\theta",
    "\\iota", "\\kappa", "\\lambda", "\\mu", "\\nu", "\\xi", "\\pi", "\\rho",
    "\\sigma", "\\tau", "\\upsilon", "\\phi", "\\chi", "\\psi", "\\omega",
    
    // 数学运算符
    "\\sum", "\\prod", "\\int", "\\oint", "\\sqrt", "\\frac", "\\lim", "\\infty",
    
    // 希腊字母大写
    "\\Gamma", "\\Delta", "\\Theta", "\\Lambda", "\\Xi", "\\Pi", "\\Sigma", "\\Upsilon", "\\Phi", "\\Psi", "\\Omega",
    
    // 常用环境
    "\\begin{equation}", "\\begin{align}", "\\begin{matrix}", "\\begin{pmatrix}", "\\begin{bmatrix}",
    "\\begin{cases}", "\\begin{tabular}", "\\begin{figure}", "\\begin{table}",
    
    // 文本格式化
    "\\textbf", "\\textit", "\\underline", "\\emph", "\\footnote",
    
    // 章节命令
    "\\section", "\\subsection", "\\subsubsection", "\\paragraph",
    
    // 其他常用命令
    "\\cite", "\\ref", "\\label", "\\hspace", "\\vspace", "\\newpage", "\\tableofcontents"
};

// 创建并填充Trie
var latexTrie = Trie();
for(i=1;#latexCommands;1){
    latexTrie.insert(latexCommands[i]);
}

// 自动补全函数
autoComplete = function(prefix) {
    var matches = latexTrie.findMatchingWords(prefix);
    return matches;
}

// 演示自动补全
testAutocomplete = function(prefix) {
    console.log("输入: " + prefix);
    console.log("补全建议:");
    var suggestions = autoComplete(prefix);
    if(#suggestions == 0) {
        console.log("没有匹配的补全建议");
    } else {
        for(i=1;#suggestions;1){
            console.log(suggestions[i]);
        }
    }
    console.log(); // 空行
}

// 测试一些常见的LaTeX前缀
testAutocomplete("\\a");
testAutocomplete("\\be");
testAutocomplete("\\int");
testAutocomplete("\\begin{");
testAutocomplete("\\text");
testAutocomplete("a");

console.pause(true);


最新回复 (1)
  • jerry2cool 1月前
    0 2
    顶!!
返回