寻求可高效查找含指定子串的字符串的数据结构

我正在寻找一种可存储字符串，并能高效查找所有包含指定子串的字符串的数据结构。示例如下：
data = ["abc", "ccc", "akro", "muhaca"] -> find("c") -> ["abc", "ccc", "muhaca"]

需要实现的C++类框架：

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

目前我仅能想到遍历所有字符串并使用std::string.find(substr)来判断是否包含子串，但想了解是否有更优的解决方案。感谢您的帮助。

优化方案推荐 #

1. 后缀自动机（Suffix Automaton） #

• 把所有存储的字符串合并构建成一个全局后缀自动机，该结构可以在**O(M)**时间内完成子串匹配（M为查询子串的长度），再通过预先建立的反向索引，将匹配结果映射回包含该子串的原字符串。
• 优势：构建的时间和空间复杂度均为O(N)（N是所有字符串的总长度），查询效率极高，适合字符串集合固定、查询频繁的场景。

2. 倒排索引（Inverted Index） #

• 预先提取所有字符串的所有子串（或限定长度的子串，如n-gram），建立「子串 -> 包含该子串的字符串列表」的映射。
• 优势：对于短子串查询，可直接**O(1)**拿到结果；实现逻辑简单直观。
• 劣势：若允许任意长度的子串查询，存储所有可能的子串会导致空间开销爆炸，更适合限定子串长度范围的场景。

3. 后缀树（Suffix Tree） #

• 将每个字符串的所有后缀插入全局后缀树，查询时定位到目标子串对应的节点，即可通过节点关联的字符串集合得到结果。
• 优势：查询效率同样为O(M)，能处理任意长度的子串查询。
• 劣势：实现复杂度高，空间开销比后缀自动机大，实际工程中较少直接实现。

4. Aho-Corasick自动机 #

• 将所有存储的字符串作为模式串构建自动机，查询时把目标子串作为输入文本，遍历自动机即可找出所有包含该子串的模式串（即存储的字符串）。
• 优势：适合多批次查询的场景，一次构建后可处理多次不同子串的查询。

与暴力解法的对比 #

暴力解法的时间复杂度为O(K*M)（K为存储的字符串数量，M为查询子串长度），当K较大或查询次数频繁时，上述结构能大幅降低单次查询的时间成本。

内容的提问来源于stack exchange，提问作者Ondrej NOHAVA