我需要一个适合字符串集合的数据结构。用户可以查询集合中具有特定前缀或后缀的字符串的当前数量，如果他们愿意，随后可以从集合中删除这些字符串。用户也可以插入一个字符串；如果多次插入一个字符串，则应返回多次。
查询操作的时间复杂度应为 O(m + log n)，其中 m 是操作结果的预期大小。
我正在考虑使用 Trie，但我们将不得不使用 2 次尝试，一次用于后缀，另一次用于前缀，该方法的问题是在这种情况下我们将无法在要求的时间内应用 remove() .
最佳答案
您需要的数据结构称为 trie，或前缀树。您可以组合两个前缀树，一个包含原始字符串，另一个包含反转字符串。搜索必须在其中一棵前缀树上执行，这取决于您需要什么 - 后缀或前缀。使用这种数据结构，您不仅可以通过后缀和前缀进行搜索，还可以找到包含任意子字符串的字符串。
关于c++ - 带有前缀和后缀查询的字符串集合的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9882556/