regex - 搜索子字符串的节省空间的方法

Question

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

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

例如，假设我有以下一组字符串:

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

搜索 a 应该返回 True，但是搜索 b 应该返回 False。我想在不将字符串存储在内存中的情况下搜索集合。

在不存储字符串的情况下，一种可能的解决方案是使用有限状态自动机 (fsa) 来表示构成集合中每个字符串的字符序列。换句话说，我将构建匹配集合中所有字符串的正则表达式。但是我不确定它是否比存储字符串更节省空间(内存)。我还想从集合中添加和删除字符串，并且重新计算 fsa 可能在计算时间方面成本太高。

我在考虑使用分类算法，例如 K-means 或 SVM，但想知道是否有任何节省空间的算法来解决这个问题。

Answer 1

用户 ruakh 在评论中发起的对话表明最好的答案是使用 trie , 某种树状数据结构。