用于搜索子字符串的高效数据结构

Question

我正在尝试找到一种保存字符串并有效查找包含给定子字符串的所有字符串的数据结构，例如：

data = ["abc", "ccc", "akro", "muhaca"]

->

find("c")

->

["abc, "ccc", "muhaca"]

class EfficientStructure {
      vector<string> find(const string & substr) const;
}

感谢您的帮助。

我唯一的想法是遍历所有字符串并使用

std::string.find(substr)

查找给定字符串是否有子字符串，但我想知道是否有更快的解决方案。

Answer 1

您必须决定是花时间进行每次搜索还是一次进行索引。

1. 每次搜索时：数据的顺序不会改变任何内容。容器将取决于您填充数据库的方式。如果你想要单一性，

   std::set<std::string>

   可能是一个不错的选择。搜索算法将是

   std::find(data.begin(), data.end(), [](std::string const& s){ return s.find(substr) != std::string::npos; })

2. 您可以构建一个索引：前缀和包含该前缀的字符串的指针列表之间的映射。然后，在搜索算法中，您只需搜索具有以子字符串开头的前缀的字符串即可。