适配两类子串查询场景的字符串集合适用数据结构咨询

最适配上述需求的是广义后缀自动机（Generalized Suffix Automaton, GSA）搭配哈希索引的组合方案，中小规模场景下也可选择实现更简单的AC自动机+哈希表方案。 #

方案适配性说明 #

核心需求匹配 #

你需要实现的StringSet类有两类核心查询能力，正好对应后缀类数据结构的典型适用场景：

• getAllStringsContainsGivenWord(String s)：查询集合中所有包含s作为子串的元素
• getAllSubstringsOfGivenWord(String s)：查询集合中所有是s子串的元素

广义后缀自动机方案优势 #

1. 空间效率最优：所有集合字符串的所有子串仅存储一份，空间复杂度为集合总字符数的线性级别，远高于暴力枚举、前缀树等方案
2. 查询效率极高：两类核心查询的耗时仅和输入字符串的长度线性相关，和集合规模无关：
   • 执行getAllStringsContainsGivenWord(s)时，将s在GSA上逐字符遍历，若能完整走完所有字符，直接取当前节点存储的关联原字符串列表即可得到结果
   • 执行getAllSubstringsOfGivenWord(s)时，将s逐字符在GSA上遍历，过程中收集所有节点关联的、存在于集合中的原字符串，去重后即为结果
3. 增删操作易实现：搭配全局哈希表存储集合内字符串的引用计数：
   • add(String s)、contains(String s)直接操作哈希表，平均时间复杂度为O(1)，新增字符串同步插入GSA并更新节点的原串关联标记
   • remove(String s)时更新哈希表引用计数，计数归零时清除GSA节点上对应的原串关联标记即可

备选AC自动机方案 #

如果希望降低实现复杂度，且集合总字符规模不大，可以选择AC自动机：

• 实现逻辑更直观：将集合中所有字符串作为模式串构建AC自动机，每个节点存储命中的模式串列表
• 查询效率同样可以达到输入长度线性级：
  • getAllSubstringsOfGivenWord(s)直接将s输入AC自动机跑匹配，收集所有命中的模式串即可
  • getAllStringsContainsGivenWord(s)将s输入AC自动机完整匹配，收集所有关联的原串即可
• 劣势：空间占用比广义后缀自动机高3~5倍，不适合超大规模字符串集合场景

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