获取与先前定义的字符串集匹配的字符串的所有前缀的高效结构

Question

假设我有一组前缀如["a", "ab", "ba", "aba", "bbb"].

我也有一个单词表。对于此列表中的每个单词，例如 "abad"，我想有效地获取该单词的所有与前缀集中的单词匹配的前缀。在这个例子中，我想作为输出 ["a","ab", "aba"].

我只想使用标准中的结构。

我正在考虑某种树结构，但我想不出一种相对轻松地实现它的方法。

Answer 1

我认为 trie 是最快的方法。但我不知道是否有 std trie。使用 trie，您可以非常快速地检查前缀。

你的 trie 看起来像这样：

红色节点是端节点...所以从顶部到红色节点是一个前缀。

如果你只会用std的东西，你可以写一个class节点。在这个 class 中你有一个 std::map 到 children。如果你的 trie 中有多个 a 和 b，地图将帮助你快速找到正确的子节点......如果你使用汉字或其他字母......（只有几个元素你最好使用 std::vector)

您还需要一种添加前缀的方法。之后你只需要一种方法来检查给定的单词是否是前缀，方法是遍历节点和地图并检查我们是否传递了红色节点。

Answer 2

正如已经提到的那样，trie 是开始查找的开始，一些 Radix tree may be, however there are a lot of options, but, unfortunately, non of them is explicitly in std. If you want to have something quick and practical, I know this article 它是针对 C# 描述的，但在 C++ 中很容易实现。

Answer 3

一个简单的实现是使用 std::unordered_set 的散列 table，然后将列表中每个单词的每个前缀与集合进行比较。

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

int main ()
{
    std::unordered_set<std::string> myPrefixes = {"a", "ab", "ba", "aba", "bbb"};

    std::vector<std::string> listOfWords;

    for (int i = 0; i < listOfWords.size(); i++) {
        std::vector<std::string> result;
        std::string word = listOfWords[i];
        for (int j = 0; j < word.length() - 1; j++) {
            if (myPrefixes.count(word.substr(0, word.length - j)) > 0) {
                result.push_back(word.substr(0, word.length - j);
            }
        }
        // print the result vector or do whatever with it
    }
    return 0;
}

Answer 4

将前缀存储在 std::vector<std::string>
std::sort()向量
对于每个感兴趣的单词，使用 std::mismatch() 来查找它们不匹配的字符，如果所有前缀都匹配，那么你就有一个匹配项
如果部分匹配，中断

您不需要任何特殊的数据结构。它会很快吗，可能不如特里那么快，它会工作吗 - 最有可能。它是否有效 - 可能 - 取决于前缀和单词。

Answer 5

这个答案通过使用 trie 来获得性能增益而增加了一点复杂性，这可能是非常巨大的。假设 M 个前缀词，每个词连同要搜索的词平均 N 个字母，使用 set 的上述过程的复杂性需要 O(N^2) 时间来查找 [= =12=]字母词。 Trie 方法，对于初始 O(MN) 预处理成本，可以将搜索降低到 O(N)。

有趣的是，Trie 构建部分（下面的 Node 结构和 insert 函数）实际上只需要 7 行。

struct Node
{
    bool is_Leaf = false;
    unordered_map<char,Node*> transitions;
};

void insert(Node* node,char* str,char* end){
    if(str==end) {node->is_Leaf = true;return ;}
    if (node->transitions[*str]==nullptr) node->transitions[*str] = new Node();
    insert(node->transitions[*str],str+1,end);
}

void search(Node* root,char* str,char* end,string so_far=""){
    if(root && root->is_Leaf) cout<<so_far<<endl;
    if(!root or str==end) return;
    so_far.push_back(*str);
    search(root->transitions[*str],str+1,end,so_far); 
}

int main(int argc, char const *argv[])
{
    Node* root = new Node();
    vector<string> prefixes = {"a", "ab", "ba", "aba", "bbb"};
    for(auto& s:prefixes) insert(root,&s[0],&s[0]+s.size());

    string to_search = "abad";
    search(root,&to_search[0],&to_search[0]+to_search.size(),"");
    return 0;
}

获取与先前定义的字符串集匹配的字符串的所有前缀的高效结构

Efficient structure to get all prefixes of a string that match a previously defined set of strings

c++

string

prefix

match