Trie及其子序列
我们有两个集合A和B.这些集合中的每一个都包含字符串。 例如：A - {“abwcd”，“dwas”，“www”}和B - {“opqr”，“tops”，“ibmd”}如何计算出现在集合A中所有字符串中的子序列，在集B中的任何字符串？ 对于上面的例子，答案是1（子序列“w”）。
所有这一切都以最佳方式进行。 我想过使用两次尝试，第一次将所有字符串的所有子序列都放在B中的t_B中，然后我开始将所有字符串的所有子序列都放在A中的t_A中，而不更新如果相同子序列之前在同一个字符串中被找到（例如：如果我有字符串“aba”，我不计算子序列“a”两次）。 这样，如果我找到一个在t_A中有n个（大小为A）外观的子序列，我检查它是否在t_B中，如果它不在，我计算它。 但是这非常慢，如果A和B的大小为15，字符串长度大约为100个字符，我的程序运行时间超过1秒。
编辑：由于任何subsqeunce结束于字符串的最后一个字符或在它之前的字符中，我们不必生成所有的子序列，但结束在字符串的最后一个字符。 当我将它们推入特里时，我注意到每个节点都是1.因此，如果我有字符串“abcd”，我只需按“abcd”，“bcd”，“cd”和“d”，因为这应该是'骨架'的特里。 但这不是一个很大的优化，我仍然在寻找更好的东西。
您不必将A中所有字符串的所有子序列放入树中。 只有投入有效的。 在添加序列之前测试序列是否有效。 我假设会员测试比添加新项目更快。 较小的特洛伊木马应该会更快地失败成员测试，所以此策略旨在尽可能快地减少特洛伊木马。
具体而言：将A中第一个字符串的所有子序列放入树中。 （为了提高效率，请使用最短的字符串作为第一个字符串）。 保留一组对所有叶节点的引用。 接下来，对于B中的所有字符串，测试每个子序列以查看它是否存在于A中。如果是，则删除该序列并且它是引用。 （从B中最长的字符串开始，尽可能快地删除trie）。
现在你有最低限度的可能性来测试。 对于A中剩余的所有字符串，测试每个子序列以查看它是否存在于trie中。 如果是，则将节点标记为有效，否则移至下一个子序列。 在每个字符串之后，从trie中删除所有无效节点，并将其余的标志重置为无效。
链接地址: http://www.djcxy.com/p/10557.html上一篇: Trie & subsequences