我们有两个集合,A和B.这些集合中的每一个都包括字符串.例如:A - {"abwcd","dwas","www"}和B - {"opqr","tops","ibmd"}我怎样才能计算A组中所有字符串中出现的子序列,但是在B组中没有任何字符串？对于上面的例子,答案是1(子序列"w").
所有这一切都以最佳方式进行.我考虑过使用两次尝试,第一次将所有字符串的所有子序列放在tr中的B中然后,我开始将所有字符串的所有子序列放在trie t_A中的A中,而不更新trie如果相同之前在同一个字符串中找到了子序列(例如:如果我有字符串"aba",我不计算子序列"a"两次).这样,如果我在t_A中找到一个n(大小为A)出现的子序列,我会检查它是否在t_B中,如果不是,我会计算它.但这非常慢,如果A和B的大小为15,字符串长度大约为100个字符,我的程序运行时间超过1秒.
编辑:由于任何子序列在字符串的最后一个字符或在它之前的字符中结束,我们不必生成所有子序列,而是以字符串的最后一个字符结尾的子序列.当我把它们推入trie时,我注意到每个节点都有1.所以如果我有字符串"abcd",我只推"abcd","bcd","cd"和"d",因为这应该是'特里的骨架.但这不是一个非常大的优化,我仍然在寻找更好的东西.
您不必将 A 中所有字符串的所有子序列放入 trie 中。只输入有效的。添加序列之前测试序列是否有效。我假设成员资格测试比添加新项目更快。较小的特里树应该更快地失败成员资格测试，因此该策略旨在尽快修剪特里树。
具体来说：将A中第一个字符串的所有子序列放入trie中。（为了提高效率，请使用最短的字符串作为第一个）。保留一组对所有叶节点的引用。接下来，对于 B 中的所有字符串，测试每个子序列以查看它是否存在于 A 中。如果存在，则删除该序列及其引用。（从 B 中最长的字符串开始，尽可能快地削减 trie）。
现在您拥有了可供测试的最小可能性集。对于 A 中的所有剩余字符串，测试每个子序列以查看它是否存在于 trie 中。如果是，则将该节点标记为有效，否则移至下一个子序列。在每个字符串之后，从 trie 中删除所有无效节点，并将其余节点上的标志重置为无效。
| 归档时间： |
|
| 查看次数： |
561 次 |
| 最近记录： |