Trie＆子序列

Question

我们有两个集合A和B.每个集合都包含字符串。 例如：A - {“abwcd”，“dwas”，“www”}和B - {“opqr”，“tops”，“ibmd”} 如何计算出现在集合A中所有字符串中的子序列，但是在集合B中没有任何字符串？对于上面的例子，答案是1（子序列“w”）。

所有这一切都以最佳方式进行。我想过使用两次尝试，第一次将所有字符串的所有子序列都放在B中的t_B中，然后我开始将所有字符串的所有子序列都放在A中的t_A中，而不更新如果相同子序列之前在同一个字符串中被找到（例如：如果我有字符串“aba”，我不计算子序列“a”两次）。这样，如果我找到一个在t_A中出现的子序列，我检查它是否在t_B中，如果不是，我计算它。但是这非常慢，如果A和B的大小为15，字符串长度大约为100个字符，我的程序运行时间超过1秒。由于任何subsqeunce都以字符串的最后一个字符结尾或在它之前的一个字符中结束，因此我们不必生成所有子序列，而是生成以字符串的最后一个字符结尾的子序列。当我将它们推入特里时，我注意到每个节点都是1.因此，如果我有字符串“abcd”，我只需按“abcd”，“bcd”，“cd”和“d”，因为这应该是'骨架'的特里。但这不是一个很大的优化，我仍然在寻找更好的东西。

Answer 1

你不应该把所有的字符串的所有子序列在阿成的线索。 只能放入有效的。在添加序列之前测试序列是否有效。我假设会员测试比添加新项目更快。较小的特洛伊木马应该会更快地失败成员测试，所以此策略旨在尽可能快地减少特洛伊木马。

具体来说： 将A中第一个字符串的所有子序列放入trie中。 （为了提高效率，请使用最短的字符串作为第一个字符串）。保留一组对所有叶节点的引用。 接下来，对于B中的所有字符串，测试每个子序列以查看它是否存在于A中。如果是，则删除该序列并且它是引用。 （从B中最长的字符串开始，尽可能快地删除trie）。

现在你有最少的一组可能要测试的。 对于A中所有剩余的字符串，测试每个子序列以查看它是否存在于trie中。如果是，则将节点标记为有效，否则移至下一个子序列。 在每个字符串之后，从trie中删除所有无效节点，并将其余的标志重置为无效。