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

Question

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

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

我只想使用来自标准的结构。

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

Answer 1

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

#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;
}