捕获一个字符串，然后匹配以该字符串开头的所有其他单词

我有一个包含 80,000 多个单词的列表，每个单词都用换行符分隔。我需要匹配每个包含较小单词作为前缀的单词。例如，

bald    <-- captures bald
balder  <-- matches because it starts with bald
balding <-- matches because it starts with bald
care    <-- captures care
cared   <-- matches because it starts with care
cares   <-- matches because it starts with care
caring  <-- does NOT match because it does not start with care

我将在 sublime text 中使用查找和替换，因此我希望能够使用“”替换所有匹配项，从而将它们从我的列表中删除。

好吧，这是背景故事：

我的单词列表基本上是英语词典的缩略版。使用正则表达式，我已经能够删除所有专有名词、缩写、带有重音字符的单词以及所有长度小于 4 个字母的单词。我将使用这本字典来制作我正在制作的 JavaScript 文字游戏。 （是的，这个is对于一个作业，但它是not为了获得学分，作业很简单，就是制作一个简单的 JavaScript 游戏。我的游戏逻辑有效，我可以手动编辑单词列表，但我希望在 2016 年之前完成，所以正则表达式似乎是可行的方法）。

游戏的目的是迫使你的对手拼完一个单词。玩家轮流将字母添加到字符串中，一旦字符串与字典中的单词匹配，游戏就会结束。因此，诸如夸大、过度和过度杀戮之类的词都是沉重的负担。一旦开销的结束被阐明，游戏就......好吧......over.

我将把 wordList 作为数组加载到 JavaScript 文件中，因此我希望它尽可能小。

我确信还有其他方法可以做到这一点（api 等），但我们不能将它们用于此作业。

任何帮助将非常感激！

存储单词列表的有效结构是前缀树 https://en.wikipedia.org/wiki/Trie。例如，给定一个像这样的字典

'car',
'card',
'carder',
'care',
'cared',
'cares',
'caring',
'can'

特里树可能看起来像这样

(where 0表示单词的结尾）。

构建 trie 的代码相当简单：

function buildTree(words) {
    var tree = {};
    words.forEach(function (word) {
        var t = tree;
        [].forEach.call(word + "0", function (char) {
            t = t[char] || (t[char] = {});
        });
    });
    return tree;
}

现在，要枚举以给定前缀开头的所有单词，只需递归遍历 trie 并收集匹配的单词：

function findWords(prefix, tree) {
    var found = [];

    function walk(pfx, t, word) {
        if (!pfx) {
            if (t[0])
                found.push(word)
            for (var c in t)
                walk("", t[c], word + c);
        } else if (pfx[0] in t)
            walk(pfx.substr(1), t[pfx[0]], word + pfx[0]);
    }

    walk(prefix, tree, "");
    return found;
}

完整代码：

function buildTree(words) {
    var tree = {};
    words.forEach(function (word) {
        var t = tree;
        [].forEach.call(word + "0", function (char) {
            t = t[char] || (t[char] = {});
        });
    });
    return tree;
}

function findWords(prefix, tree) {
    var found = [];

    function walk(pfx, t, word) {
        if (!pfx) {
            if (t[0])
                found.push(word)
            for (var c in t)
                walk("", t[c], word + c);
        } else if (pfx[0] in t)
            walk(pfx.substr(1), t[pfx[0]], word + pfx[0]);
    }

    walk(prefix, tree, "");
    return found;
}

words = [
    'car',
    'card',
    'carder',
    'care',
    'cared',
    'cares',
    'caring',
    'can'

]

prefixTree = buildTree(words);
document.write(findWords("care", prefixTree));

要删除以另一个单词开头的单词，您可以按照上面的方式构建 trie，然后遍历它，在终止标记后剪切一次搜索（0）发现：

function buildTree(words) {
    var tree = {};
    words.forEach(function (word) {
        var t = tree;
        [].forEach.call(word + "0", function (char) {
            t = t[char] || (t[char] = {});
        });
    });
    return tree;
}


function findShortWords(tree) {
    var found = [];

    function walk(t, word) {
        if(t[0]) {
            found.push(word);
            return;
          }
        for (var c in t)
            walk(t[c], word + c);
    }

    walk(tree, "");
    return found;
}

words = [
    'card',
    'carder',
    'care',
    'cared',
    'cares',
    'caring',
    'can',
    'canoe',
    'bald',
    'balder',
    'balding',
    'foo'

]

prefixTree = buildTree(words);

document.write(findShortWords(prefixTree));