空间高效的方式来搜索子字符串

Question

我有一组可变长度的字符串，我想验证一个可变长度的前缀字符串存在于该集合中的至少一个字符串。可以在连续搜索之间添加字符串。

难点在于我不想存储集合的字符串，而是存储集合的空间高效表示。

举个例子，假设我有以下字符串集：

S = {"abcd","aaaaaaaaa","dcba"} 

寻找a应该返回True，但搜索b应该返回False。我想要搜索集合而不将字符串存储在内存中。

不存储字符串，一个可能的解决方案是使用有限状态自动机（fsa）来表示使集合中的每个字符串的字符序列。换句话说，我将构建匹配集合中所有字符串的正则表达式。但是我不确定它会比存储字符串更有效率（内存）。我也想添加和删除集合中的字符串，并且重新计算fsa在计算时间方面可能代价太高。

我在考虑使用分类算法，如K均值或SVM，但想知道是否有任何空间高效的算法来解决这个问题。

Answer 1

用户ruakh在评论中开始的对话揭示了最好的答案是使用trie这种特定类型的树型数据结构。