我们有两个集合A和B。每个集合都包含字符串。
例如：A - {"abwcd", "dwas", "www"} 和 B - {"opqr", "tops", "ibmd"}
我该如何计算在集合A的所有字符串中出现，但在集合B的任何字符串中都没有出现的子序列数量？对于上面的例子，答案是1（即子序列"w"）。
要以最优的方式完成这一任务。我考虑使用两个Trie树，第一次将B集合中所有字符串的所有子序列放入Trie t_B中，然后，我开始将A集合中所有字符串的所有子序列放入Trie t_A中，如果在同一字符串中之前找到了相同的子序列（例如：如果我有字符串“aba”，我不会将子序列“a”计算两次），则不更新Trie树。这样，如果我发现一个子序列在t_A中出现了n次（其中n是A的大小），我检查它是否在t_B中，如果不在，则计数。但是这非常慢，如果A和B的大小为15，并且字符串长度约为100个字符，我的程序运行时间超过1秒。
编辑：由于任何子序列都以字符串的最后一个字符或其之前的字符结尾，因此我们不必生成所有子序列，而只需要生成以字符串的最后一个字符结尾的子序列。当我将它们推入Trie树时，我用1标记每个节点。因此，如果我有字符串“abcd”，我只推入“abcd”，“bcd”，“cd”和“d”，因为这应该是Trie树的“骨架”。但是这不是一个非常大的优化，我仍在寻找更好的方法。
要以最优的方式完成这一任务。我考虑使用两个Trie树，第一次将B集合中所有字符串的所有子序列放入Trie t_B中，然后，我开始将A集合中所有字符串的所有子序列放入Trie t_A中，如果在同一字符串中之前找到了相同的子序列（例如：如果我有字符串“aba”，我不会将子序列“a”计算两次），则不更新Trie树。这样，如果我发现一个子序列在t_A中出现了n次（其中n是A的大小），我检查它是否在t_B中，如果不在，则计数。但是这非常慢，如果A和B的大小为15，并且字符串长度约为100个字符，我的程序运行时间超过1秒。
编辑：由于任何子序列都以字符串的最后一个字符或其之前的字符结尾，因此我们不必生成所有子序列，而只需要生成以字符串的最后一个字符结尾的子序列。当我将它们推入Trie树时，我用1标记每个节点。因此，如果我有字符串“abcd”，我只推入“abcd”，“bcd”，“cd”和“d”，因为这应该是Trie树的“骨架”。但是这不是一个非常大的优化，我仍在寻找更好的方法。